Next: Searching kd trees
Up: Closest Point Search
Previous: Closest Point Search
kd trees
kd 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 kd tree. If the query
consists of point
, kd 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].

Subsections
root
20070531