# 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.

#### Extracted Text

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-4

## Upcoming Pages

Here’s what’s next.

## Search Inside

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 September 21, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT Libraries Government Documents Department.