Chapter 10. Spatial Tree Structures
The algorithms in this chapter are concerned primarily with modeling twodimensional structures over the Cartesian plane to conduct powerful search queries that go beyond simple membership, as covered in Chapter 5. These algorithms include:
 Nearest neighbor

Given a set of twodimensional points, P, determine which point is closest to a target query point, x. This can be solved in O(log n) instead of an O(n) bruteforce solution.
 Range queries

Given a set of twodimensional points, P, determine which points are contained within a given rectangular region. This can be solved in O(n^{0.5} + r) where r is the number of reported points, instead of an O(n) bruteforce solution.
 Intersection queries

Given a set of twodimensional rectangles, R, determine which rectangles intersect a target rectangular region. This can be solved in O(log n) instead of an O(n) bruteforce solution.
 Collision detection

Given a set of twodimensional points, P, determine the intersections between squares of side s centered on these points. This can be solved in O(n log n) instead of an O(n^{2}) bruteforce solution.
The structures and algorithms naturally extend to multiple dimensions, but this chapter will remain limited to twodimensional structures for convenience. The chapter is named after the many ways researchers have been able to partition ndimensional data using the intuition at the heart of binary search trees.
Nearest Neighbor Queries
Given a set of points, ...
Get Algorithms in a Nutshell, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.