Region search returns dataset points inside a specified region of multidimensional space. Typical regions include hyper-spheres, defined by distance from a center, and hyper-rectangles, defined by coordinate ranges. section 9.3.6
Implement region search by traversing the spatial index and pruning branches that cannot intersect the query region:
- For a k-d tree, test each point, visit the nearer branch, then visit the other branch only when its split boundary intersects the region. section 9.3.6
- For an SS-tree, test region–node-envelope intersection and inspect individual points only at leaves. section 10.4.2
Complexity and trade-offs
A small region may follow one balanced-tree path in O(log n), while a region containing every point requires O(n) traversal. Thus the worst-case running time is O(n), although pruning can be substantial for selective regions. Regions bounded by generic, non-axis-parallel lines require more complex methods than k-d-tree search. section 9.3.6
