Algorithms in a Nutshell

Range Queries | 297

Computational

Geometry

Situation 3: Empty region

We construct a query region from a single random point drawn uniformly

from the same values for the input set. Performance results are shown in

Table 9-8. The kd-tree executes nearly instantaneously; all recorded execu-

tion times are less than a fraction of a millisecond.

Figure 9-26. Comparing kd-tree versus brute force for situation 2

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