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


19

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(n2))O(nlogn)O(nlogn)

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(nlogn)

Odpowiedzi:


0

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.Rreϵ0ϵP.κfa(ϵ/2),P.)O(nlogn)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.


O(nlogn)

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.