Existe-t-il un algorithme O (n log n) pour la simplification des lignes 4D?

L' algorithme Ramer-Douglas-Peucker pour la simplification de ligne a le pire cas d' exécution . Pour des entrées aléatoires convenablement réparties, il s'est attendu à une complexité d'exécution O ( n log n ) . En 2D, il existe d'autres algorithmes avec la pire complexité d'exécution O ( n log n ) , qui calculent exactement le même résultat que l'algorithme Ramer-Douglas-Peucker. Étant donné que ces algorithmes sont basés sur une structure de données à "trajectoire (convexe) coque", il n'est pas évident qu'ils puissent être généralisés aux lignes 4D.$O(n^2)$$O(n \log n)$$O(n \log n)$

Existe-t-il un algorithme (randomisé) qui a (attendu) runtime (indépendant de l'entrée) pour le cas des lignes 4D? Vous pouvez supposer des distances euclidiennes et une tolérance absolue globale.$O(n \log n)$

L'algorithme qui fonctionne avec le cas 4D est décrit dans l'article Algorithmes d'approximation du temps quasi-linéaire pour la simplification des courbes par quatre auteurs: Pankaj K.Agarwal, Sariel Har-Peled, Nabil H. Mustafa et Yusu Wang .

Étant donné une courbe polygonale dans R d et un paramètre ϵ ≥ 0 , une simplification ϵ de P avec une taille au plus κ F ( ϵ / 2 , P ) peut être construite en temps O ( n log n ) et O ( n ) espace.$P$$\mathcal R^d$$\epsilon \ge 0$$\epsilon$$P$$\mathcal \kappa_F(\epsilon/2, P)$$\mathcal O(n\log n)$$\mathcal O(n)$

L'algorithme ne dépend pas des propriétés de monotonie. Il couvre la ligne d'origine avec des disques et recherche la traversée de ligne sur l'ensemble ordonné.

$\mathcal O(n\log n)$