Das nächste Punktepaar in 3+ Dimensionen (Teilen und Erobern)

Question

Ich habe Mühe, meinen Kopf darüber zu wickeln, wie der Divide and Conquer-Algorithmus für Dimensionen größer als 2 funktioniert, insbesondere wie man das nächste Punktepaar zwischen zwei Probleme.

Ich weiß, dass ich nur Punkte innerhalb einer Entfernung d der Teilung zwischen den beiden auf der x Achse berücksichtigen müssen.

Ich weiß, dass im 3d Fall ich jeden Punkt zu nur 15 anderen vergleichen muss.

Was ich nicht verstehe, ist, wie man diese 15 Punkte wählt. Im Fall 2d sortiert man die Werte einfach nach dem Wert y und durchläuft sie der Reihe nach. Im Fall 3d muss jedoch jeder Punkt mit den 15 am nächsten liegenden Punkten auf den Achsen yundz verglichen werden. Ich kann keinen Weg finden, um zu bestimmen, was diese 15 Punkte in einer Weise sind, die keinen Worstfall von O(n^2) hat ...

Was fehlt mir hier?

Answer 1

Eine einfache Lösung besteht darin, einen Octree- oder einen K-D-Baum mit allen Punkten zu erstellen und ihn dann zu verwenden, um den nächsten Punkt für jeden Punkt zu finden. Das ist O (N * log N) für den Durchschnittsfall.

Eine schnellere Lösung, die ich denke, ist O (N) für den durchschnittlichen Fall kann unter Berücksichtigung der folgenden Idee umgesetzt:

Wenn Sie den Platz in die Hälfte (etwa durch eine Achse ausgerichtet Ebene) partitionieren, erhalten Sie die Punkte unterteilt in zwei Teilmengen, A und B, und die zwei nächsten Punkte können sowohl in A, beide in B oder eins in A und eins in B sein.

So müssen Sie eine Warteschlange von Paaren von 3D-Boxen erstellen , geordnet nach dem Mindestabstand zwischen ihnen und dann:

1) Wählen Sie das erste Paar von Boxen aus der Warteschlange

2) Wenn beide Boxen die gleiche Box A sind, teilen Sie sie in zwei Boxen B und C in zwei Hälften und schieben Sie die Paare (B, B), (C, C) und (B, C) in die Warteschlange.

3) Wenn sie unterschiedlich sind (A, B), dividiere den größten (zum Beispiel B) in die Hälfte, indem du die Felder C und D erhältst und die Paare (A, C) und (A, D) in die Warteschlange verschiebst .

4) Wiederholen.

Wenn die Anzahl der Punkte innerhalb des Boxenpaars unter einen Schwellenwert fällt, können Sie mit Brachialgewalt das nächste Punktepaar finden.

Die Suche stoppt, sobald der Abstand zwischen den beiden Boxen im oberen Paar größer ist als der bisher gefundene Mindestabstand.