Den entferntesten Punkt in einem Satz von einem anderen Satz finden

Question

Mein Ziel ist eine effizientere Implementierung des Algorithmus gestellt in this question.

Betrachten zwei Sätze von Punkten (in N-Raum. 3-Raum für den beispielhaften Fall von RGB-Farbraum, während eine Lösung für 1-space 2-Raum nur in der Abstandsberechnung unterscheidet). Wie findest du den Punkt in der ersten Menge, der im zweiten Satz am weitesten von seinem nächsten Nachbarn entfernt ist? In einem 1-Platz-Beispiel wäre die Antwort 8 angesichts der Sätze A: {2,4,6,8} und B: {1,3,5}, da 8 3 Einheiten entfernt ist 5 (der nächste Nachbar in B), während alle anderen Mitglieder von A nur 1 Einheit von ihrem nächsten Nachbarn in B entfernt sind. Edit: 1-space ist übermäßig vereinfacht, da die Sortierung sich auf Distanz bezieht, so dass sie nicht höher ist Maße.

Die Lösung in der Ausgangsfrage beinhaltet einen Brute-Force-Vergleich von jedem Punkt in einer Menge (alle R, G, B mit 512> = R + G + B> = 256 und R% 4 = 0 und G% 4 = 0 und B% 4 = 0) zu jedem Punkt in der anderen Menge (colorTable). Ignoriere für diese Frage, dass der erste Satz programmatisch ausgearbeitet wird, anstatt wie der zweite Satz als gespeicherte Liste durchlaufen zu werden.

Answer 1

Zuerst müssen Sie den nächsten Nachbarn jedes Elements in dem anderen Satz finden.

Um dies effizient zu tun, benötigen Sie einen nearest neighbor Algorithmus. Persönlich würde ich eine kd-tree implementieren, nur weil ich es in der Vergangenheit in meiner Algorithmus-Klasse getan habe und es war ziemlich einfach. Eine andere brauchbare Alternative ist ein R-tree.

Tun Sie dies einmal für jedes Element im kleinsten Satz. (Fügen Sie ein Element vom kleinsten zum größeren hinzu und führen Sie den Algorithmus aus, um den nächsten Nachbarn zu finden.)

Daraus sollten Sie in der Lage sein, eine Liste der nächsten Nachbarn für jedes Element zu erhalten.

Während Sie die Paare der nächsten Nachbarn finden, bewahren Sie sie in einer sortierten Datenstruktur auf, die eine schnelle Additionsmethode und eine schnelle getMax-Methode wie heap, sortiert nach Euclidean distance, hat.

Dann, sobald Sie fertig sind, fragen Sie einfach den Haufen für die max.

die Laufzeit für diese setzt sich wie folgt zusammen:

N = Größe des kleineren Satz
M = Größe der größeren eingestellt

• N * O (log M + 1) für alle der nächste Nachbar des kd-Baums prüft.
• N * O (1) zum Berechnen der euklidischen Distanz vor dem Hinzufügen zum Heap.
• N * O (log N) zum Hinzufügen der Paare in den Heap.
• O (1), um die endgültige Antwort zu bekommen: D

Also am Ende der ganze Algorithmus O (N * log M) ist.

Wenn Sie sich nicht um die Reihenfolge jedes Paares kümmern, können Sie ein wenig Zeit und Platz sparen, indem Sie nur den max gefundenen Wert beibehalten.

* Haftungsausschluss: Dies alles setzt voraus, dass Sie nicht eine enorm hohe Anzahl von Dimensionen verwenden und dass Ihre Elemente einer meist zufälligen Verteilung folgen.

Answer 2

EDIT: Ich meinte nlog (n), wobei n die Summe der Größen beider Sätze ist.

Im 1-Raum-Set ich Sie so etwas wie dieses (Pseudo-Code) tun könnte

eine Struktur wie diese

Verwenden

Struct Item { 
    int value 
    int setid 
} 

(1) Max Entfernung = 0
(2) Lesen Sie alle die Sätze in Item-Strukturen
(3) ein Array von Zeigern auf alle Elemente erstellen
(4) Sortieren der Array von Zeigern von Item-> Wertfeld der Struktur
(5) Walk das Array aus wenn so eingestellt MaxDistance auf diese Entfernung

Return Anfang bis Ende überprüft, wenn die Item-> setid aus dem vorherigen Item- unterscheidet> setId if (SetIDs sind unterschiedlich)
überprüfen, ob dieser Abstand größer ist als Max Abstand ist der maximale Abstand.

Answer 3

Der offensichtlichste Ansatz scheint mir zu sein, eine Baumstruktur auf einem Satz zu erstellen, damit Sie sie relativ schnell durchsuchen können. Ein kd-tree oder ähnliches wäre wahrscheinlich dafür geeignet.

Nachdem Sie das getan haben, gehen Sie über alle Punkte im anderen Satz und verwenden den Baum, um den nächsten Nachbarn im ersten Satz zu finden, wobei Sie das Maximum verfolgen, während Sie gehen.

Es ist nlog (n), den Baum zu erstellen, und log (n) für eine Suche, so dass das Ganze in nlog (n) laufen sollte.

Answer 4

Um die Dinge effizienter zu gestalten, sollten Sie einen Pigeonhole-Algorithmus verwenden - gruppieren Sie die Punkte in Ihrer Referenzmenge (Ihre colorTable) nach ihrer Position im n-Raum. Auf diese Weise können Sie effizient den nächsten Nachbarn finden, ohne alle Punkte durchlaufen zu müssen.

Zum Beispiel, wenn Sie in 2-Raum gearbeitet haben, teilen Sie Ihr Flugzeug in ein 5 x 5 Raster, geben 25 Quadrate mit 25 Gruppen von Punkten.

Teilen Sie in 3 Feldern Ihren Würfel in ein 5 x 5 x 5 Raster und geben Sie 125 Würfel mit jeweils einer Reihe von Punkten.

Dann, um Punkt n zu testen, finden Sie das Quadrat/Würfel/Gruppe, die n enthält und Testabstand zu diesen Punkten. Sie müssen nur Punkte von benachbarten Gruppen testen, wenn der Punkt n näher am Rand liegt als der nächste Nachbar in der Gruppe.

Answer 5

Für jeden Punkt in der Serie B, finden den Abstand zu seinem nächsten Nachbarn in der Serie A.

Um den Abstand zu jedem nächsten Nachbarn finden Sie so lange eine kd-tree verwenden kann als die Anzahl der Dimensionen angemessen ist, Es gibt nicht viele Punkte, und Sie werden viele Fragen stellen - sonst wird es zu teuer sein, den Baum zu bauen, um sich zu lohnen.

Answer 6

Vielleicht verstehe ich die Frage nicht, aber wäre es nicht einfach, das Vorzeichen an allen Koordinaten in einem Datensatz umzukehren (dh einen Koordinatensatz mit -1 zu multiplizieren), dann den ersten nächsten Nachbarn zu finden (Was wäre der entfernteste Nachbar)? Sie können Ihren bevorzugten knn-Algorithmus mit k = 1 verwenden.