Is there an O(n log n) algorithm for 4D line simplification?

Question

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.

Answer 1

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.

Sidenote:
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.