Algorithms in a Nutshell

(^284) | Chapter 9: Computational Geometry
Context
When comparing this approach against a brute-force approach that compares the
distances between query pointxand each pointp∈P, there are two important
costs to consider: (1) the cost of constructing the kd-tree, and (2) the cost of
locating the query pointxwithin the tree structure. The tradeoffs that impact
these costs are:
Number of dimensions
As the number of dimensions increases, the cost of constructing the kd-tree
overwhelms its utility. Some authorities believe that for above 20 dimen-
sions, this approach is less efficient than a straight comparison against all
points.
Number of points in the input set
When the number of points is small, the cost of constructing the structure
may outweigh the improved performance.
Forces
Binary trees can remain efficient search structures because they can be balanced as
nodes are inserted into and deleted from the tree. Unfortunately, kd-trees cannot
be balanced so easily, because of the deep structural information about the dimen-
sional plane that they represent. The ideal solution is to construct the initial kd-tree
so that either (a) the leaf nodes are at the same level in the tree, or (b) all leaf
nodes are within one level of all other leaf nodes. Example 9-4 contains the imple-
mentation of the well-known technique that uses recursion to iterate over each of
the coordinate dimensions. Simply put, it selects the median element from a set of
points to represent the node; and the elements “below” the median are inserted
into the left subtree, whereas elements “above” the median are inserted into the
right subtree. The code works for arbitrary dimensions.
Example 9-4. Recursively construct a balanced kd-tree
public class KDFactory {
// Known comparators for partitioning points along dimensional axes.
private static Comparator comparators[];
// Recursively construct KDTree using median method on input points.
public static KDTree generate (IMultiPoint []points) {
if (points.length == 0) { return null; }
// median will be the root.
int maxD = points[0].dimensionality( );
KDTree tree = new KDTree(maxD);
// Make dimensional comparators that compare points by ith dimension
comparators = new Comparator[maxD+1];
for (int i = 1; i <= maxD; i++) {
comparators[i] = new DimensionalComparator(i);
}
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
Licensed by
Ming Yi