Cover by Gary Pollice, Stanley Selkow, 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

O'Reilly logo

Range Queries

Given a rectangular range R defined by [xlow, ylow, xhigh, yhigh] and a set of points P, which points in P are contained within the rectangle R? A brute-force algorithm that inspects all points in P can determine the enclosed points in O(n)—can we do better? For the Nearest Neighbor problem, we organized the points into a kd-tree to process nearest neighbor queries in O(log n) time. Using the same data structure, we now show how to process Range Query problems over the Cartesian plane in

image with no caption

where r is the number of points reported by the query. Indeed, when the input set contains d-dimensional data points, the solution scales to solve d-dimensional Range Query problems in O(n1-1/d+r). Figure 9-24 illustrates.

Range Queries fact sheet

Figure 9-24. Range Queries fact sheet

Input/Output

Input

A set of n points P in d-dimensional space and a d-dimensional hypercube that specifies the desired range query.

Output

The full set of points enclosed by the range query. The points do not appear in any specific order.

Assumptions

The range queries are aligned properly with the axes in the d-dimensional data set since they are specified by d individual ranges, for each dimension of the input set.

Context

Because kd-trees become unwieldy for a large number of dimensions, this algorithm and overall approach is likely ...

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