Opheim simplification ( Line Simplification): Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: The only auxiliary space used is the current search ray and the current best, the distances from the next point to the ray and to the ray's origin, candidate point to stay in the simplified line) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1981 == Reference == http://dx.doi.org.ezproxy.canberra.edu.au/10.2312/eg.19811012") |
No edit summary |
||
| Line 23: | Line 23: | ||
== Model of Computation == | == Model of Computation == | ||
Real RAM | |||
== Year == | == Year == | ||
Latest revision as of 07:54, 10 April 2023
Time Complexity
$O(n)$
Space Complexity
$O({1})$
(Derived: The only auxiliary space used is the current search ray and the current best, the distances from the next point to the ray and to the ray's origin, candidate point to stay in the simplified line)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Real RAM
Year
1981
Reference
http://dx.doi.org.ezproxy.canberra.edu.au/10.2312/eg.19811012