Ramer–Douglas–Peucker algorithm

Like most line fitting, polygonal approximation or dominant point detection methods, it can be made non-parametric by using the error bound due to digitization and quantization as a termination condition.

[2] Assuming the input is a one-based array: The algorithm is used for the processing of vector graphics and cartographic generalization.

But a self-intersection could occur if the accepted approximation is not sufficiently fine which led to the development of variant algorithms.

Using (fully or semi-) dynamic convex hull data structures, the simplification performed by the algorithm can be accomplished in O(n log n) time.

[6] Given specific conditions related to the bounding metric, it is possible to decrease the computational complexity to a range between O(n) and O(2n) through the application of an iterative method.