O'Reilly logo

Algorithms in a Nutshell, 2nd Edition by Stanley Selkow, Gary Pollice, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 10. Spatial Tree Structures

The algorithms in this chapter are concerned primarily with modeling two-dimensional 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 two-dimensional 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) brute-force solution.

Range queries

Given a set of two-dimensional points, P, determine which points are contained within a given rectangular region. This can be solved in O(n0.5 + r) where r is the number of reported points, instead of an O(n) brute-force solution.

Intersection queries

Given a set of two-dimensional rectangles, R, determine which rectangles intersect a target rectangular region. This can be solved in O(log n) instead of an O(n) brute-force solution.

Collision detection

Given a set of two-dimensional 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(n2) brute-force solution.

The structures and algorithms naturally extend to multiple dimensions, but this chapter will remain limited to two-dimensional structures for convenience. The chapter is named after the many ways researchers have been able to partition n-dimensional data using the intuition at the heart of binary search trees.

Nearest Neighbor Queries

Given a set of points, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required