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 leaves provide a complete disjunct partition of the points. These leaves are called buckets (cf. Fig. 2). Furthermore, every node contains the limits of the represented point set.

Figure: Left: Recursive construction of a k-d tree. If the query consists of point $\mathbf{p}_q$, k-d tree search has to backtrack to the tree root to find the closest point. Right: Partitioning of a point cloud. Using the cut (b) rather than (a) results in a more compact partition and a smaller probability of backtracking [7].