Algorithms in a Nutshell

Range Queries | 295

Computational

Geometry

It is difficult to produce sample data sets to show the performance of RANGE

QUERY. We demonstrate the effectiveness of RANGEQUERYon a kd-tree by

comparing its performance to a brute-force implementation that inspects each

point against the desired query region. Thed-dimensional input set for each of

these situations containsnpoints whose coordinate values are drawn uniformly

from the range [0,s], wheres=4,096. There are three situations we evaluate:

Figure 9-25. Expected performance for O(n1-1/d) algorithm

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