Array partition rearranges an array around a pivot: elements in one part compare smaller than the pivot and elements in the other compare larger. In k-d tree construction, the comparison coordinate changes with recursion depth, using coordinate level % k. section 9.3.3
A balanced recursive construction applies partition as follows:
- Choose the median on the coordinate selected by the current level. section 9.3.3
- Recursively partition each side at the next level; do not sort once and repeatedly split, because the comparison coordinate changes. section 9.3.3
Partitioning two-dimensional points
For the points [(0,5),(1,-1),(-1,6),(-0.5,0),(2,5),(2.5,3),(-1,1),(-1.5,-2)], choose (-0.5,0) as the first-coordinate median. The left array contains [(-1,1),(-1.5,-2),(-1,6)], and the right array contains [(1,-1),(2.5,3),(2,5),(0,5)]. The next partition compares second coordinates.
