Line Simplification: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Line Simplification (Line Simplification)}} == 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 == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |...") |
No edit summary |
||
| Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
$n$: number of points representing the curve/line initially | |||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 16: | Line 16: | ||
|- | |- | ||
| [[Ramer–Douglas–Peucker algorithm ( Line Simplification)|Ramer–Douglas–Peucker algorithm]] || 1972 || $O(n^{2})$ || $O(n)$ | | [[Ramer–Douglas–Peucker algorithm ( Line Simplification)|Ramer–Douglas–Peucker algorithm]] || 1972 || $O(n^{2})$ || $O(n)$ || Exact || Deterministic || [https://www.sciencedirect.com/science/article/abs/pii/S0146664X72800170 Time] | ||
|- | |- | ||
| [[Visvalingam–Whyatt ( Line Simplification)|Visvalingam–Whyatt]] || 1993 || $O(n^{2})$ || $O(n)$ || Exact || Deterministic || [https://hull-repository.worktribe.com/output/459275 Time] | | [[Visvalingam–Whyatt ( Line Simplification)|Visvalingam–Whyatt]] || 1993 || $O(n^{2})$ || $O(n)$ || Exact || Deterministic || [https://hull-repository.worktribe.com/output/459275 Time] | ||
Latest revision as of 07:52, 10 April 2023
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 |