Graphics Reference
In-Depth Information
optimally solved using either one of these two methods. Of the two, Prim's algo-
rithm is probably both conceptually simpler and easier to implement. It starts with
any vertex from the initial set and grows a tree from it by finding the lowest cost edge
between an unconnected vertex and the tree. This edge and the vertex are then con-
nected to the tree and the process is repeated until all vertices have been connected.
For additional details on computing MSTs, including descriptions of both Prim's and
Kruskal's algorithms, see [Cormen90] and the delightful topic of [Skiena98].
6.2.2.3 Bottom-up
n
-ary Clustering Trees
One interesting method utilizing an MST calculation as a key step is the bottom-up
clustering method presented in [Garcia99]. Given a set of
n
bounding spheres, this
method begins by constructing the adjacency graph between the spheres. The edges
of this graph contain grouping costs (described in material to follow) between pairs
of spheres. From the graph, an MST is calculated, from which in turn a hierarchy of
spheres is constructed.
As the number of edges in the complete adjacency graph is
O
(
n
2
), which would
severely impact the running time of the MST algorithm, Garcia et al. limit the number
of connections each bounded object can have to some constant number
k
, reduc-
ing the complexity to
O
(
n
). By using an appropriate space-partitioning strategy, the
reduction could be limited to be approximately the
k
-nearest neighbors and still run
in
O
(
n
) time.
A clustering function is associated with the remaining edges. Given two spheres
S
i
and
S
j
— with radii
r
i
and
r
j
, respectively, and with a distance
d
ij
between their
centers — Garcia et al. first define the attraction between
S
i
and
S
j
as
a
ij
=
r
i
r
j
d
ij
.
This attraction measure becomes larger the larger and closer the two spheres are,
mimicking an intuitive perception of how clusters would form.
To avoid large clusters being created early in the build process, the final clustering
function is defined as
r
ij
/
a
ij
, where
r
ij
is the radius of the smallest bounding sphere
encompassing
S
i
and
S
j
. This helps in penalizing the grouping of two spheres of high
attraction when their resulting bounding sphere would be very large.
Once the adjacency graph with associated edge costs has been formed, the MST
of the graph is computed. The edges of the MST are then sorted in ascending order
of cost. From the sorted edges they construct what they call a binary clustering tree
(BCT) by considering an edge at a time, combining the two nodes associated with
the edge into a new cluster. If a node is already part of a cluster, the existing cluster
is grouped into the new cluster instead of the node. As clusters are formed, they are
bounded by the smallest bounding sphere containing the bounding spheres of the
nodes. They are also assigned the cost of the connecting edge as a grouping cost.
The construction of the BCT from the MST takes
O
(
n
log
n
) time.
At this point it would be possible to stop and use the resulting binary tree. However,
as described, a final step of the algorithm converts the BCT into an
n
-arytreeby
merging connected clusters that have similar grouping costs under a single node.
