Sortierung nach euklidischer Entfernung

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

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. $x$ $y$ $y \in S$

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

cg.comp-geom sorting Alex K.
quelle

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

$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:

Lösung 1: Finden Sie die senkrechten Winkelhalbierenden zwischen Punktpaaren und konstruieren Sie die Anordnung dieser Linien. Die Anordnung hat 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 und die Abfragezeit ist $\Theta(n^2)$ $\Theta(n^4)$ $O(n^4)$ . $O(\log n)$

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 $\Theta(n)$ Zellen, von denen jede mit hoher Wahrscheinlichkeit von 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 . $\Theta(n^2)$ $O(n)$ $O(n^3)$

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 $\sum_i O(1+\log k_i)$ $k_i$ die Anzahl der Punkte ist, die mit dem Punkt außerhalb der Reihenfolge liegen . Aber ist (jede nicht abgetastete Halbierende verursacht höchstens ein Punktpaar außerhalb der Reihenfolge), also die Abfragezeit $y_i$ $\sum k_i$ $O(n)$ ist auch . $\sum_i O(1+\log k_i)$ $O(n)$

David Eppstein
quelle

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

Startpunkten in

Zeit sortieren und die Ergebnisse in einer Hash-Tabelle speichern können, indem Sie den Raum

für eine konstante Suche verwenden?

n^{4}

$n^4$

n

$n$

O (n^{2} \log n)

$O(n^2\log n)$

O (n^{2})

$O(n^2)$

Dave

Weil es

Startpunkte mit unterschiedlicher Sortierreihenfolge gibt, nicht

Θ (n^{4})

$\Theta(n^4)$

Θ (n^{2})

$\Theta(n^2)$

David Eppstein

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) Regionen ergeben, und daher wird die Suche nach "Ihrer" Region durch eine sinnvolle Suchtechnik erfordern $n\log(n)$ $O(n!)$ Zeit. (EDIT: $O(\log(n!)) = O(n\log(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

Θ (n^{4})

$\Theta(n^4)$

O (n!)

$O(n!)$

Θ (n^{2})

$\Theta(n^2)$

@ 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