Sortierung nach euklidischer Entfernung

17

ist eine Menge von Punkten in einer Ebene. Ein zufälliger Punkt x S ist auf derselben Ebene gegeben. Die Aufgabe besteht darin, allenach dem euklidischen Abstand zwischenundzu sortieren.SxSx yySxy

Ein No-Brain-Ansatz besteht darin, die Abstände zwischen und für alle zu berechnen und sie dann mit einem beliebigen schnellen Algorithmus zu sortieren.y y SxyyS

Gibt es eine Möglichkeit, zu speichern oder vorzuverarbeiten, damit der Sortiervorgang schneller wird?S

Alex K.
quelle
1
Sie können ein Raster mit der entsprechenden Größe betrachten und Punkte anhand des entsprechenden Quadrats gruppieren (z. B. mithilfe einer Hash-Tabelle). Dann können Sie für bestimmte Paare von Quadraten schließen, dass alle Punkte von einem Quadrat weiter von als alle Punkte von einem anderen Quadrat. In der Praxis könnte es helfen, denke ich. x
Ilyaraz
Der von Ihnen angegebene „No-Brain-Ansatz“ läuft in der Zeit O (n log n), wobei n die Anzahl der Punkte in S ist, was in der Praxis meiner Meinung nach ziemlich schnell ist. Möchten Sie den log n -Faktor deaktivieren, oder möchten Sie etwas anderes wie externe Sortierung ?
Tsuyoshi Ito
Der Punkt ist, dass ich praktisch unbegrenzte Zeit habe, um meinen Satz von Punkten vorzubereiten, aber die Zeit, um sie zu sortieren, ist sehr begrenzt. Trotzdem ist jede Beschleunigung der Standardsortierung erwünscht - auch wenn sie gleich O (n log n) ist, aber im schlimmsten Fall (oder im besten Fall oder was auch immer) schneller.
Alex K.
Wenn ich zum Beispiel S als 2D-Baum speichere, kann ich einen nächsten Nachbarn in der Zeit O (log n) finden. Vielleicht gibt es eine ähnliche Lösung für meine Aufgabe. Ich bin kein großer Experte für Geodatenstrukturen - und es gibt so viele -, dass ich es leicht übersehen könnte.
Alex K.

Antworten:

13

Lösung 1: Finden Sie die senkrechten Winkelhalbierenden 2 ) zwischen Punktpaaren und konstruieren Sie die Anordnung dieser Linien. Die Anordnung hat Θ ( n 4 ) Zellen, innerhalb derer die sortierte Reihenfolge konstant ist. Erstellen Sie daher eine Punktlokalisierungsdatenstruktur für die Anordnung und dekorieren Sie jede Zelle mit der sortierten Reihenfolge, die für Punkte in dieser Zelle zurückgegeben werden soll. Die sortierten Reihenfolgen zwischen benachbarten Zellen unterscheiden sich nur in einer einzelnen Transposition, sodass Sie eine beständige Datenstruktur verwenden können, damit die Darstellungen dieser sortierten Reihenfolgen den Raum teilen können. Der gesamte Speicherplatz ist O ( n 4 ) und die Abfragezeit ist OΘ(n2)Θ(n4)O(n4) .O(logn)

Lösung 2: Wählen Sie eine Zufallsstichprobe von dieser senkrechten Winkelhalbierenden, konstruieren Sie ihre Anordnung und unterteilen Sie jede Anordnungszelle durch vertikale Liniensegmente durch jede Kreuzung von zwei abgetasteten Linien. Die resultierende Partition hat Θ ( nΘ(n) Zellen, von denen jede mit hoher Wahrscheinlichkeit von O ( n ) nicht abgetasteten Bisektorengekreuzt wird. Dekorieren Sie jede Zelle der Partition nach einer gültigen sortierten Reihenfolge der Punkte, wie von einigen x innerhalb der Zelle aus gesehen. Der Gesamtraum ist O ( n 3 ) .Θ(n2)O(n)O(n3)

Um nun eine Abfrage durchzuführen , suchen Sie den Abfragepunkt in der Partition, suchen Sie die in der Partitionszelle gespeicherte Reihenfolge und verwenden Sie den Sortieralgorithmus für den kartesischen Baumvergleich von Levcopoulos & Petersson (1989), beginnend mit dieser gespeicherten Reihenfolge. Die Zeit für diesen Schritt ist proportional zu wobei k iiO(1+logki)ki die Anzahl der Punkte ist, die mit dem Punkt außerhalb der Reihenfolge liegen . Aber k i ist O ( n ) (jede nicht abgetastete Halbierende verursacht höchstens ein Punktpaar außerhalb der Reihenfolge), also die AbfragezeityikiO(n) ist auch O ( n ) .iO(1+logki)O(n)

David Eppstein
quelle
1
PS: Hier ist eine alternative Variante von Lösung 2, die denselben Speicherplatz und dieselbe Abfragezeit verwendet,
David Eppstein,
Warum wird vorverarbeitet, wenn Sie von allen n Startpunkten in O ( n 2 log n ) Zeit sortieren und die Ergebnisse in einer Hash-Tabelle speichern können, indem Sie den Raum O ( n 2 ) für eine konstante Suche verwenden?n4nO(n2logn)O(n2)
Dave
Weil es Startpunkte mit unterschiedlicher Sortierreihenfolge gibt, nicht Θ ( n 2Θ(n4) . Θ(n2)
David Eppstein
1

Sie werden wahrscheinlich nicht in der Lage sein, von time wegzukommen, wie Sie es in Scheiben schneiden; Selbst die Vorausberechnung von Regionen, die allen möglichen Sortierreihenfolgen entsprechen, könnte (glaube ich) O ( n ! ) Regionen ergeben, und daher wird die Suche nach "Ihrer" Region durch eine sinnvolle Suchtechnik O ( log ( n ! ) ) = erfordernnlog(n)O(n!) Zeit. (EDIT:O(log(n!))=O(nlog(n))das ist absolut falsch; Weitere Informationen finden Sie in der hervorragenden Antwort von David Eppstein!) Ein nützlicher Weg, um die Komplexität zu verringern. Dies gilt insbesondere dann, wenn Sie nicht die vollständige Sortierung auf einmal benötigen, sondern nur in der Lage sein müssen, ten-nächsten zufällig herauszuziehen on the fly - könnte durch Voronoi-Diagramme höherer Ordnung gehen: Erweiterungen der Standard-Voronoi-Zelle, die nicht nur den nächsten Nachbarn, sondern auch den zweitnächsten aufnehmen usw. Frank Dehnes Artikel über die Suche nach k-nächsten Nachbarn, http: //people.scs .carleton.ca / ~ dehne / publications / 2-02.pdf scheint die kanonische Referenz zu sein; Seine Homepage unter http://www.dehne.carleton.ca/publications enthält eine Reihe weiterer Artikel zu Voronoi-Diagrammen, die von Nutzen sein könnten.k

Steven Stadnicki
quelle
3
Θ(n4)O(n!)Θ(n2)
@ David Ich denke, Sie sollten dies eine Antwort machen.
James King
Abgeordnet - n! Ich fühlte mich falsch, als ich es schrieb, aber ich konnte keinen Fall dagegen sehen. Ich werde meine Antwort in Kürze ändern, um dies zu korrigieren, aber ich würde gerne eine direktere Antwort erhalten. Danke!
Steven Stadnicki