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.