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

Start Free Trial

No credit card required