A pivot is a selected element whose value determines how a collection is divided during partitioning. In a binary search tree, the pivot becomes a node; its left and right subtrees represent the two resulting partitions. section 9.2 section 9.2.1
In multidimensional partitioning, a pivot also determines the coordinate used for the split:
- Split a two-dimensional region vertically by comparing points’ x coordinates, or horizontally by comparing their y coordinates. section 9.2
- Cycle through dimensions or directions at successive levels, using a perpendicular split for the next pivot. section 9.2
- Associate each pivot with the region formed by its ancestors’ partitions; deeper pivots cover progressively smaller regions. section 9.2.1
Alternating spatial splits
Choose point R as the first pivot and split vertically. Choose point W in the left partition and split it horizontally; choose point P in the resulting upper-left region and split vertically again. The same process turns Opal City into a k-d tree root and Civic City into a child created by the next perpendicular split. section 9.2
