Czy istnieje algorytm O (n log n) dla uproszczenia linii 4D?

Algorytm Ramer Douglasa-Peucker dla linii Uproszczenie najgorszy czasem przebiegu. W przypadku odpowiednio rozmieszczonych losowych danych wejściowych oczekiwał złożoności środowiska wykonawczego O ( n log n ) . W 2D istnieją inne algorytmy o najgorszym przypadku złożoności środowiska wykonawczego O ( n log n ) , które obliczają dokładnie taki sam wynik jak algorytm Ramera-Douglasa-Peuckera. Ponieważ algorytmy te są oparte na strukturze danych „kadłuba (wypukłego) kadłuba”, nie jest oczywiste, czy można je uogólnić na linie 4D.$O(n^2)$$O(n \log n)$$O(n \log n)$

Czy istnieje (losowy) algorytm, który ma (oczekiwany) czas działania (niezależnie od danych wejściowych) w przypadku linii 4D? Możesz założyć odległości euklidesowe i globalną absolutną tolerancję.$O(n \log n)$

Algorytm, który działa z przypadkiem 4D, opisano w artykule Algorytmy aproksymacji czasu bliskiego liniowego dla uproszczenia krzywej przez czterech autorów: Pankaja K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa i Yusu Wanga .

Biorąc pod uwagę, wielokątny krzywa w R d i parametr ε ≥ 0 An ε -simplification o P o wielkości co najwyżej κ F ( ε / 2 , P ) mogą być skonstruowane w O ( N log N ) czasu i O ( n ) przestrzeń.$P$$\mathcal R^d$$\epsilon \ge 0$$\epsilon$$P$$\mathcal \kappa_F(\epsilon/2, P)$$\mathcal O(n\log n)$$\mathcal O(n)$

Algorytm nie zależy od właściwości monotonicznych. Obejmuje oryginalną linię dyskami i poszukuje przejścia linii na zamówionym zestawie.

$\mathcal O(n\log n)$