Interactive spatial partitioning for O(log n) range queries and nearest-neighbor search
KD-Tree: Binary space-partitioning tree for organizing points in k-dimensional space
Splits: Alternates between vertical (x) and horizontal (y) at each level
Complexity: O(log n) for search operations
Recursively split the space by selecting median points. At each level, alternate between splitting on x-axis (vertical) and y-axis (horizontal). This creates a balanced binary tree.
Traverse down the tree to find the leaf containing the query point. Then backtrack, checking if there could be closer points on the other side of any splitting plane.
Recursively search the tree, pruning branches that cannot intersect the query region. This avoids checking all points, achieving O(log n + k) where k is results found.