Is there an O(n log n) algorithm for 4D line simplification?
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.