Suppose you need to find nearby points on a map. Each point has an x coordinate and a y coordinate: numerical components that locate it along two dimensions. A vertical split compares x coordinates; a horizontal split compares y coordinates. Either comparison can divide points into groups, but neither coordinate alone describes where a point lies in the plane. section 8.4.2 section 9.2
Using only x for every split throws away useful information. Points close together across a vertical boundary can land in different groups, while points far apart vertically can share the same x coordinate. A k-d tree addresses this by changing which coordinate it compares at successive levels. section 8.4.2 section 9.2
To index points with k coordinates:
- Store each point as a tuple of k comparable coordinate values. section 9.2.1
- Choose a point as the pivot for a region. Compare one coordinate to place other points in its two partitions. section 9.2
- At tree level i, compare coordinate i mod k. In two dimensions, splits therefore alternate between x and y. section 9.2 section 9.2.1
A split changes direction
Start with a vertical line through a pivot, grouping points by their x coordinates. Within one of those resulting regions, choose another pivot and split horizontally by y coordinate. The second split divides only that region—not the entire plane. Repeating this process makes each tree node responsible for a progressively restricted region. section 9.2 section 9.2.1
Coordinate choice also matters when modifying the tree. To replace a deleted node, finding the minimum for its split coordinate is not necessarily a walk down left children: descendant levels compare different coordinates, so the relevant minimum may be elsewhere in the subtree. The stated cost of finding that minimum is O(n^(1−1/k)). section 9.3.4
Figure 9.2 Partitioning points in the 2-D Cartesian space by cycling through the directions along which we split. For the first split (left) we choose point R and draw a vertical line (parallel to y axis, x coordinate is constant) passing through it. We have thus created two half-spaces, a lighter-shaded one on the left and a darker-shaded one on the right of this line, grouping points W, P, O, Q, U on one side, and S, T on the other. Point R is the pivot of this partitioning. Next, we choose point W in the lighter shade partition. This time, we draw a horizontal line (parallel to x axis, y coordinate is constant). It splits the lighter shade partition into two new partitions, one in the top-left area of the plane, containing P, O and U, and one in the bottom-left area, with just Q. If we further split the top-left area at point P, we again need to use a vertical line, as shown in the right-most part of the figure.
Follow the vertical, horizontal, then vertical splits to see how successive coordinate comparisons subdivide existing regions. section 9.2
