The Ramer-Douglas-Peucker algorithm for line simplification has worst-case $O(n^2)$ runtime. For suitably distributed random inputs, it has expected $O(n \log n)$ runtime complexity. In 2D, there are other algorithms with worst case $O(n \log n)$ runtime complexity, which compute exactly the same result as the Ramer-Douglas-Peucker algorithm. Since these algorithms are based on a "path (convex) hull" datastructure, it is not obvious whether they can be generalized to 4D lines.

Is there a (randomized) algorithm which has (expected) $O(n \log n)$ runtime (independent of input) for the case of 4D lines? You may assume Euclidean distances and a global absolute tolerance.


The algorithm that works with 4D case is described in the article Near-Linear Time Approximation Algorithms for Curve Simplification by four authors: Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa, and Yusu Wang.

Given a polygonal curve $P$ in $\mathcal R^d$ and a parameter $\epsilon \ge 0$, an $\epsilon$-simplification of $P$ with size at most $\mathcal \kappa_F(\epsilon/2, P)$ can be constructed in $\mathcal O(n\log n)$ time and $\mathcal O(n) $ space.

The algorithm does not depend on monotonicity properties. It covers the original line with disks and seeks the line traversal on the ordered set.

There is a modification of Douglas-Peucker algorithm with the worst-case in $\mathcal O(n\log n)$ described in the paper An O(n log n) Implementation of the Douglas-Peucker Algorithm for Line Simplification. by John Hershberger and Jack Snoeyink: improved DP line simplification. Indeed it uses path hull.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.