Algorithms in a Nutshell

Nearest Neighbor Queries | 283

Computational

Geometry

Output

Given the pointsP, a kd-tree is computed. For each query pointx, a point inPis

output as being the closest neighbor tox.

Assumptions

If two points are “too close” to each other through floating-point error, the algo-

rithm may incorrectly select the wrong point; however, the distance to the actual

closest point would be so close that there should be no impact by this faulty

response.

Figure 9-20. Nearest Neighbor Query fact sheet

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