Algorithms in a Nutshell

Range Queries

Given a rectangular range R defined by [x_low, y_low, x_high, y_high] 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

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(n^1-1/d+r). Figure 9-24 illustrates.

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 ...