$k$d-trees

$k$D-trees are a generalization of binary search trees. Every node represents a partition of a point set to the two successor nodes. The root represents the whole point cloud and the leafs are a disjunct partition of the set. These leafs are called buckets (cf. Fig. ). Furthermore, every node contains the limits of the represented point set. An efficient implementation of a $k$d-tree is given in [19].

Figure: Left: Construction of a $k$d tree. Right: The optimized $k$d-tree uses splits along the longest axis to ensure compact volumes.

Searching in $k$d-trees is done recursively. A given 3D point $\V p_q$ needs to be compared with the separating plane in order to decide on which side the search must continue. This procedure is executed until the leafs are reached. There, the algorithm has to evaluate all bucket points. However, the closest point may be in a different bucket, iff the distance to the limits is smaller than the one to the closest point in the bucket. In this case backtracking has to be performed. Fig. shows a backtracking case, where the algorithms has to go back to the root. The test is known as Ball-Within-Bounds test [6,11,14].