Graphics Reference
In-Depth Information
6.2.2.2 Other Bottom-up Construction Strategies
When grouping two objects under a common node, the pair of objects resulting in
the smallest bounding volume quite likely corresponds to the pair of objects nearest
each other. As such, the merging criterion is often simplified to be the pairing of the
query node with its nearest neighbor.
Locating the point (or object) out of a set of points closest to a given query point
is known as the
nearest neighbor problem
. This problem has been well studied, and
many different approaches have been suggested. For a small number of objects, a
low-overhead brute-force solution is preferred. For larger numbers, solutions based
on bucketing schemes or
k
-d trees are typically the most practical. A
k
-d tree solution
is quite straightforward to implement (see Section 7.3.7 for details). The tree can be
built top down in, on average,
O
(
n
log
n
) time, for example by splitting the current
set of objects in half at the object median.
A nearest neighbor query is limited to the relevant parts of the
k
-d tree by keeping
track of a bound for the nearest object found so far (see Section 7.3.7). Initially, this
value is set to the distance from the query object to the root node object. As closer
objects are found, the bound is decreased accordingly. Halfspaces farther away than
the bound distance are pruned away, as they cannot possibly contain a nearer object.
When neither halfspace can be discarded, the halfspace containing the query object is
usually descended into first, as this is more likely to lead to the bound being lowered
and the search sped up.
The
k
-nearest neighbor problem can be solved by the same basic method just by
adding a priority queue of
k
objects that keeps track of the
k
-nearest objects seen so
far, updating the bound distance from the last (farthest) element of the queue. On
average, both search and insertion into a
k
-d tree can be performed in
O
(log
n
) time.
k
-d trees are discussed further in Chapters 7 and 13.
With the methods presented earlier, no guarantees were made as far as tree balance
was concerned, and it is in fact easy to find input configurations that cause degenerate
trees. Tree balance can be improved by forming not just one but several pairs of closest
points during each iteration. For instance, when all possible
n
/2 pairs are formed at
each iteration the resulting tree becomes balanced. This would also reduce the number
of iterations needed to form the tree, from
O
(
n
)to
O
(log
n
), improving construction
time. As forming all possible pairs would result in a worse tree over just forming one
pair, a good compromise is to form
k
pairs for some small value of
k
.
For forming larger clusters of objects, specific clustering algorithms can be used.
One such approach is to treat the objects as vertices of a complete graph and compute
a
minimum spanning tree
(MST) for the graph, with edge weights set to the distance
between the two connected objects or some similar clustering measure. The MST is
then broken into components by deleting edges that are“too long,”and the remaining
set of disjoint (but internally connected) components are the object clusters.
The MST can be computed using, for instance,
Prim's algorithm
or
Kruskal's algo-
rithm
. Both of these are greedy algorithms, meaning that they always select to perform
the locally best-looking alternative. Greedy algorithms often perform quite well on
most problems, but they are not generally optimal. However, the MST problem is
