Algorithms in a Nutshell

(^294) | Chapter 9: Computational Geometry
The code shown in Example 9-6 is a modified tree traversal that potentially visits
every node in the tree. Because the kd-tree partitions thed-dimensional data set in
hierarchical fashion, there are three decisions RANGEQUERYmakes at each noden:
Is the region associated with node n fully contained within the query region?
When this happens, thesearchtraversal can stop because all descendant
points belong to the query result. The helper methoddrainexecutes a full
traversal of the subtree rooted atn to add all of these points to the result set.
Does the query region contain the point associated with node n?
If so, add the point associated withn to the result set.
Along the dimension d represented by node n, does query region intersect n?
It can do so in two ways: if the query region seeks points to the left ofd, then
traverse thebelowsubtree ofn. If the query region seeks points to the right of
d, then traverse theabove subtree.
Analysis
It is possible that the query region contains all points in the tree, in which case all
nodes are visited by thedrainmethod; this leads to O(n) performance. However,
when RANGEQUERYdetects that the query region does not intersect an indi-
vidual node within the kd-tree, it can prune the traversal. The cost savings
depends upon the number of dimensions and the specific nature of the input set.
It has been shown (Preparata and Shamos, 1985) that RANGEQUERYusing kd-
trees performs in O(n1-1/d+r) whereris the number of results found. As the number
of dimensions increases, the benefit decreases. Figure 9-25 graphs the expected
performance of an O(n1-1/d) algorithm; the distinctive feature of the graph is fast
performance for small values ofdthat over time inexorably approaches O(n).
Because of the addition ofr(the number of points returned by the query), the
actual performance will deviate from the ideal curve shown in Figure 9-25.
// recursively progress along both ancestral trees, if demanded.
// The cost in manipulating space to be "cropped" to the proper
// structure is excessive. Leave alone, with no impact on computation.
if (space.getLeft(dimension) < coord) {
if (below != null) { below.search(space, results); }
}
if (coord < space.getRight(dimension)) {
if (above != null) { above.search(space, results); }
}
}
/* Visit all descendant nodes in the tree rooted at given node. /
private void drain(ArrayList results) {
if (below != null) { below.drain (results); }
results.add(this.point);
if (above != null) { above.drain (results); }
}
Example 9-6. Range Query implementation (continued)
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