Binary partitioning divides a collection or spatial region into two subsets using a selected coordinate or dividing value. In a k-d tree, each pivot creates two child regions: points below or left of the pivot and points above or right of it. section 9.2
A useful multidimensional partitioning scheme follows these rules:
- Split one coordinate at a time: use a vertical line for x, a horizontal line for y, and cycle through coordinates in higher dimensions. section 9.2
- Store the pivot at the tree node and assign the two resulting subregions to its left and right subtrees. section 9.2
- Prefer splits that produce subsets of approximately equal size; repeated good splits yield logarithmic tree height, while poor insertion order can produce linear height. section 9.2.2
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.
A two-dimensional diagram shows successive vertical and horizontal splits, pivots, and the points assigned to each resulting region. section 9.2
