A region is the subset of search-space values associated with a tree node. In a binary search tree or k-d tree, the node’s pivot and ancestor partitions determine which searches pass through it. section 9.2.1
Regions become progressively smaller as tree construction adds pivots:
- The root covers the entire dataset or search space. section 9.2.1
- Each child covers a partition created by its parent’s pivot; deeper nodes cover smaller partitions. section 9.2.1
- For a queried point, every node on its search path covers that point, while the stopping node covers the smallest corresponding region. section 9.2.1
Alternating spatial partitions
In a two-dimensional k-d tree, one pivot can split a map vertically; a child then splits its partition horizontally. The child therefore represents a top or bottom sub-region within the parent’s region.
