Gibt es einen O (n log n) -Algorithmus zur Vereinfachung von 4D-Linien?

19

Der Ramer-Douglas-Peucker-Algorithmus zur Leitungsvereinfachung hat die Worst-Case- Laufzeit O(n2) . Für geeignet verteilte zufällige Eingaben wurde eine Laufzeitkomplexität von erwartet . In 2D gibt es andere Algorithmen mit der Laufzeitkomplexität ungünstigsten Fall , die genau dasselbe Ergebnis wie der Ramer-Douglas-Peucker-Algorithmus berechnen. Da diese Algorithmen auf einer "Pfad (konvex) Hülle" -Datenstruktur basieren, ist es nicht offensichtlich, ob sie auf 4D-Linien verallgemeinert werden können.O(nLogn)O(nLogn)

Gibt es einen (randomisierten) Algorithmus mit (erwarteter) Laufzeit (unabhängig von der Eingabe) für den Fall von 4D-Zeilen? Sie können von euklidischen Abständen und einer globalen absoluten Toleranz ausgehen.O(nLogn)

Thomas Klimpel
quelle

Antworten:

0

Der Algorithmus, der mit 4D-Fällen arbeitet, wird in dem Artikel Nahezu lineare Zeitnäherungsalgorithmen zur Vereinfachung von Kurven von vier Autoren beschrieben: Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa und Yusu Wang .

Bei einer Polygonkurve in R d und einem Parameter ϵ 0 kann eine ϵ -Vereinfachung von P mit einer Größe von höchstens κ F ( ϵ / 2 , P ) in der Zeit O ( n log n ) und O ( n ) konstruiert werden. Platz.PRdϵ0ϵPκF(ϵ/2,P)O(nLogn)O(n)

Der Algorithmus hängt nicht von den Monotonieeigenschaften ab. Es deckt die ursprüngliche Linie mit Scheiben ab und sucht die Linie, die auf dem bestellten Satz durchquert wird.


O(nLogn)

Böse
quelle