Line Simplification (Line Simplification)

From Algorithm Wiki
Jump to navigation Jump to search


Line simplification is the process of taking a line/curve as represented by a list of points and reducing the number of points needed to accurately represent the given line.


$n$: number of points representing the curve/line initially

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Ramer–Douglas–Peucker algorithm 1972 $O(n^{2})$ $O(n)$ Exact Deterministic Time
Visvalingam–Whyatt 1993 $O(n^{2})$ $O(n)$ Exact Deterministic Time
Reumann–Witkam 1974 $O(n)$ $O({1})$ Exact Deterministic
Opheim simplification 1981 $O(n)$ $O({1})$ Exact Deterministic Time
Lang simplification 1969 $O(n)$ $O({1})$ Exact Deterministic
Zhao-Saalfeld 1997 $O(n)$ $O(n)$ Exact Deterministic Time