A generic algorithm for constructing hierarchical representations of geometric objects Page: 4 of 9
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to Digital Library by the UNT Libraries Government Documents Department.
The following text was automatically extracted from the image on this page using optical character recognition software:
Submitted to 1996 IEEE Int'l Conf on Robotics and Automation
2.2 The Clustering Algorithm
There are other factors we might want to consider in
determining the priority of merging a pair of nodes. We
define the Balance of a node to be the greater ratio of
diameters of its children. We define the Fill of a node to
be the ratio of its diameter to the sum of the diameters of
its children. These measures can be used in assigning the
Cost of merging a pair of nodes. The cost is associated
with the p-set wrapper of the would-be new node. We
have been experimenting with a Cost of the form:
Cost = diameterA x (B x Fill + C x Balance), (2)
where A, B, and C, are non-negative constants.
Roughly, increasing A improves spatial balance of the
hierarchy. B and C are used to tune the emphases on
spatial coherence and structural balance.
To speed the algorithm, instead of using convex hulls
for the geometric extent of nodes and L2 distance to
measure gaps, we can use axis-aligned bounding boxes
and L.. distance. We will use the term body to refer to
a node, its p-set wrapper, and the set contained by that
node. We now sketch the algorithm.
1. Let GLimit be the maximum gap allowed between
two bodies to be merged. This must be positive
if the data may contain more than one connected
component. Let DLimit be the maximum diameter
of bodies eligible for merging.
2. If there is only one parent-less body, return it; it
is the root of the Subset Tree. Otherwise, let the
set of active bodies ABods be the set of parent-less
bodies that obey DLimit. Let rest of the parent-less
bodies form the set of dormant bodies DBods.
3. Let CSize = DLimit + GLimit. Subdivide the
bounding box of the input into voxels of edge-
length CSize to create a body-center occupancy ar-
ray. Then scan in the centers of the active bodies to
determine possible eligible pairs, and use the gap
limit GLimit to filter these to obtain the queue of
eligible pairs MPairs sorted by increasing Cost.
4. Until MPairs is empty do the following:
(a) Pop off the first pair in MPairs, and remove
other pairs that share an element with this
pair. Create a merged body from this pair.
(b) If this body meets the DLimit criterion, then
add it to the set ABods and determine which
other members of ABods it is eligible to merge
with, using and updating the array from step
3. Enqueue the new eligible pairs in MPairs.
(c) Otherwise, add the new body to DBods.
5. Double DLimit and GLimit. Go to 2.
2.3 Subset Tree Analysis
We now present an informal analysis of the algorithm.
Since the hierarchy is a binary tree with N leaves,
exactly N - 1 interior nodes are created, and at most
N bodies (nodes) are active at any time. Let us assume
that during the construction no body is eligible to merge
with more than k other bodies for some constant k that
depends on how "pathological" the input is. We justify
the assumption by considering the case in which input is
uniformly sized and uniformly distributed and in which
(2) is simplified to be diameter. The key observation is
that because DLimit doubles in step 4 and the ordering
of MPairs favors the creation of roughly cuboid bodies,
doubling the DLimit and GLimit in step four does not,
on average, increase the number of bodies any one body
is eligible to merge with.
The assumption justified, it follows that the maxi-
mum length of the queue MPairs is kN, and at most
kN queue operations are performed. These operations
take total time O(kN(log k + log N)) time. Further-
more, consulting the array of lists in steps 3 and 4(b)
also takes a constant amount of time dependent on k for
each body. We note that the array can be implemented
virtually with a spatial hash table, using array coordi-
nates as keys and cell contents as data; thus, the storage
for the array only really need be size O(N). The other
operations are constructing the geometric extents of the
bodies, merging them, and determining the diameters
and gaps. Assuming that we use axis-aligned bounding
boxes, each takes constant time. Since all other indi-
vidual operations are constant time, the total running
time is then O(kN(log K + logN), or O(N log N) for
a given quality of input. In the worst case, with "patho-
logical" inputs such as a box of spaghetti, the constant
k is replaced by N. Thus the worst case running time
is O(N2log N). Finally, ordering of MPairs also bal-
ances the tree to be of 0(log N) depth, with the constant
depending on the Cost function and the quality of the in-
Here’s what’s next.
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Xavier, P.G. A generic algorithm for constructing hierarchical representations of geometric objects, article, October 1, 1995; Albuquerque, New Mexico. (digital.library.unt.edu/ark:/67531/metadc664081/m1/4/: accessed December 11, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT Libraries Government Documents Department.