Balanced k-d tree construction recursively chooses a coordinate-wise median as each pivot, then builds subtrees from the points on either side. The comparison coordinate advances with the recursion level, typically using level modulo k. section 9.3.3
The construction follows a small set of implementation steps:
- Partition the points around a median using the coordinate selected by the current level. section 9.3.3
Two-dimensional partition
For eight points, choosing (-0.5, 0) as the first-coordinate median leaves four points on each side. The left subtree then partitions its three points by the second coordinate, choosing (-1, 1) as its median. section 9.3.3
