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



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


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


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.


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

Get Algorithms in a Nutshell now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.