Line Simplification (Line Simplification)
Jump to navigation
Jump to search
Description
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.
Parameters
$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 |