Algorithms in a Nutshell

(^292) | Chapter 9: Computational Geometry
Range Queries
Given a rectangular rangeRdefined by [xlow,ylow,xhigh,yhigh] and a set of points
P, which points inPare contained within the rectangleR? A brute-force algo-
rithm that inspects all points inPcan determine the enclosed points in O(n)—can
we do better? For the NEARESTNEIGHBORproblem, we organized the points into
a kd-tree to process nearest neighbor queries in O(logn) time. Using the same
data structure, we now show how to process RANGEQUERYproblems over the
Cartesian plane in
whereris the number of points reported by the query. Indeed, when the input set
containsd-dimensional data points, the solution scales to solved-dimensional
RANGEQUERY problems in O(n1-1/d+r). Figure 9-24 illustrates.
Figure 9-24. Range Queries fact sheet
O()nr+
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use