Ramer–Douglas–Peucker algorithm ( Line Simplification)

Time Complexity

$O(n^{2})$

Space Complexity

$O(n)$

(Derived: Recursive algorithm that has a worst-case recursion tree depth of O(n), and O(1) info stored per level)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Real RAM

Year

1972

Reference

https://www.sciencedirect.com/science/article/abs/pii/S0146664X72800170