Auf derWikipedia-Eintrag für k-d-Bäumewird ein Algorithmus zum Durchführen einer Suche nach dem nächsten Nachbarn in einem k-d-Baum vorgestellt. Was ich nicht verstehe, ist die Erklärung von Schritt 3.2. Woher wissen Sie, dass es keinen näheren Punkt gibt, nur weil der Unterschied zwischen der Aufteilungskoordinate des Suchpunkts und dem aktuellen Knoten größer ist als der Unterschied zwischen der Aufteilungskoordinate des Suchpunkts und dem aktuell besten?

Nächste-Nachbarn-Suche Animation der NN-Suche mit einem KD-Baum in 2D

Der Algorithmus für den nächsten Nachbarn (NN) zielt darauf ab, den Punkt im Baum zu finden, der einem bestimmten Eingabepunkt am nächsten liegt. Diese Suche kann effizient durchgeführt werden, indem die Baumeigenschaften verwendet werden, um große Teile des Suchraums schnell zu entfernen. Die Suche nach einem nächsten Nachbarn in einem kd-Baum geht wie folgt vor:

Beginnend mit dem Wurzelknoten bewegt sich der Algorithmus rekursiv im Baum nach unten, genau wie beim Einfügen des Suchpunkts (dh nach rechts oder links, je nachdem, ob der Punkt größer oder kleiner als der aktuelle Knoten in der Liste ist aufgeteilte Dimension).Sobald der Algorithmus einen Blattknoten erreicht, speichert er diesen Knotenpunkt als den "aktuell besten".Der Algorithmus löst die Rekursion des Baums auf und führt die folgenden Schritte an jedem Knoten aus: 1. Wenn der aktuelle Knoten näher als der aktuell beste ist, wird er der aktuell beste. 2. Der Algorithmus prüft, ob sich auf der anderen Seite der Teilungsebene Punkte befinden, die näher am Suchpunkt liegen als die aktuell besten. Konzeptionell geschieht dies, indem die aufteilende Hyperebene mit einer Hypersphäre um den Suchpunkt herum geschnitten wird, deren Radius dem aktuell nächstgelegenen Abstand entspricht. Da die Hyperebenen alle achsenausgerichtet sind, wird dies als einfacher Vergleich implementiert, um festzustellen, ob die Differenz zwischen der Aufteilungskoordinate des Suchpunkts und dem aktuellen Knoten geringer ist als der Abstand (Gesamtkoordinaten) vom Suchpunkt zum aktuell besten. 1. Wenn die Hypersphäre die Ebene überquert, befinden sich möglicherweise nähere Punkte auf der anderen Seite der Ebene. Daher muss der Algorithmus den anderen Zweig des Baums vom aktuellen Knoten nach näheren Punkten abwärts bewegen und dabei denselben rekursiven Prozess wie beim ausführen gesamte Suche. 2. Wenn die Hypersphäre die Aufteilungsebene nicht schneidet, wandert der Algorithmus weiter den Baum entlang und der gesamte Zweig auf der anderen Seite dieses Knotens wird eliminiert.Wenn der Algorithmus diesen Vorgang für den Stammknoten abgeschlossen hat, ist die Suche abgeschlossen.

Im Allgemeinen verwendet der Algorithmus zum Vergleich quadratische Abstände, um die Berechnung von Quadratwurzeln zu vermeiden. Darüber hinaus kann die Berechnung gespart werden, indem der bestmögliche Abstand zum Quadrat in einer Variablen zum Vergleich gehalten wird.