Suche im 3D-Baum.

Nachdem der Baum aufgebaut wurde, müssen nun Funktionen zur Verfügung gestellt werden, um die nächsten Punkte zu finden. Dies führt zum Konzept der Reichweitensuche (engl.: range search). Jeder Knoten des Baumes repräsentiert eine Region durch einen Quader. Die Aufgabe besteht darin, zu einem 3D-Punkt den nächstgelegenen Punkt zu finden, dessen Abstand den Wert $d$ nicht überschreitet. Dazu wird um den gegebenen Punkt herum eine Suchregion der Größe $d \times d \times d$ aufgebaut. Falls die Suchregion vollständig innerhalb des Quaders eines Teilbaumes liegt, setzt sich die Suche nur dort fort. Dagegen werden beide Teilbäume durchsucht, falls die Suchregion auf beiden Seiten der Trennebene liegt. In Anhang B.1.2 sind Ausschnitte des Programmcodes des beschriebenen Algorithmus zu finden.