Lang simplification ( Line Simplification)

Time Complexity

$O(n)$

Space Complexity

$O({1})$

(Derived: The only auxiliary space used is the current search line and the distance from a point in the search interval to the search line, which is all $O(1)$ space)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Real RAM

Year

1969

Reference

-