Algorithms in a Nutshell

(^288) | Chapter 9: Computational Geometry
computed so far; this method (found in this book’s code repository) exits immedi-
ately when a partial computation of the Euclidean distance exceeds the minimum
found.
Consequences
Assuming the initial kd-tree is balanced, the search can advantageously discard up
to half of the points in the tree during the recursive invocations. Note that there
will be times that two recursive invocations are required, but only in the case
where the computed minimum distance is just large enough to cross over the
dividing line for a node, in which case both sides need to be explored to find the
closest point.
Analysis
The kd-tree is initially constructed as a balanced kd-tree, where the dividing line
on each level is derived from the median of the points remaining at that level.
Locating the parent node of the target query can be found in O(logn)by
traversing the kd-tree as if the point were to be inserted. However, note that the
algorithm at times makes two recursive invocations: one for the above child and
one for the below child. If the double recursion occurs frequently, the algo-
rithm degrades to be O(n), so it is worth understanding how often it can occur.
The multiple invocations only occur when the perpendicular distance,dp, from
the target point to the node’s point is less than the best computed minimum. As
the number of dimensions increases, there are more potential points that satisfy
these criteria. Table 9-6 provides some empirical evidence to describe how often
this occurs. A balanced kd-tree is created fromn=4 to 131,072 random two-
dimensional points generated within the unit square. A set of 50 nearest point
queries is issued for a random point within the unit square, and Table 9-6 records
the average number of times two recursive invocations occurred (that is, when
dp<min[0] and the node in question has both an above and a below child), as
compared to single recursive invocations.
Table 9-6. Ratio of double recursion invocations to single
n
d=2
#Recursions
d=2
#Double recursion
d=10
#Recursion
d=10
#Double recursion
4 1.54 0.54 1.02 1
8 2.8 1.08 1.04 3
16 4.3 1.36 1.48 6.84
32 5.66 2.14 1.86 14.58
64 8.08 2.58 3.54 30.42
128 9.24 2.58 8.64 60.06
256 10.36 2.42 25.42 109.9
512 11.76 2.8 52.44 222.44
1,024 13.2 3.06 122.32 421.68
2,048 15.48 3.22 244.54 730.84
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