Algorithms in a Nutshell

(^282) | Chapter 9: Computational Geometry
A kd-tree is a recursive binary tree structure whose nodes contain points and a
coordinate label (i.e., eitherxory) that determines the partitioning line. The root
node represents the rectangular region [xlow=–∞,ylow=–∞,xhigh=+∞,yhigh=+∞]in
the plane partitioned along the vertical lineVthrough point p 1. The left subtree
further partitions the region to the left ofV, whereas the right subtree further
partitions the region to the right of theV. The left child of the root represents a
partition along the horizontal lineHthrough p 2 that subdivides the region to the
left ofVinto a region above the lineHand a region below the lineH. The region
[–∞,–∞,p 1 .x,+∞] is associated with the left child of the root, whereas the region
[p 1 .x,–∞,+∞,+∞] is associated with the right child of the root. These regions are
effectively nested, and one can see that the region of an ancestor node wholly
contains the regions of any of its descendant nodes.
When these kd-trees are properly constructed, nodes on levelireflect rectangles
that are roughly twice as large as the rectangles on leveli+1. This property will
enable the NEARESTNEIGHBORalgorithm (depicted in Figure 9-20) to efficiently
search for a target point in O(logn) performance because it will be able to discard
entire subtrees containing points that are demonstrably too far to be the closest
point. In the upcoming section “Range Queries,” we will see how the structure
improves the performance of range queries over the points.
Input/Output
Input
A set of two-dimensional pointsPin a plane. A set of nearest neighbor queries
(not known in advance) is issued one at a time to find the nearest point inPto a
pointx.
Figure 9-19. Division of two-dimensional plane using kd-tree
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