Graphics Reference
In-Depth Information
9.3.1
The Dobkin-Kirkpatrick Hierarchy
The Dobkin-Kirkpatrick (DK) hierarchy of a
d
-dimensional polyhedron
P
is a
sequence
P
0
,
P
1
,
...
,
P
k
of nested increasingly smaller polytopal approximations of
P
, where
P
P
0
and
P
i
+
1
is obtained from
P
i
by deletion of a subset of the vertices
of
P
i
. The subset of vertices is selected to form a maximal set of independent vertices
(that is, such that no two vertices in the set are adjacent to each other). The construc-
tion of the hierarchy stops with the innermost polyhedron
P
k
being a
d
-simplex (a
tetrahedron, in 3D). [Edelsbrunner87] shows that every polyhedron allows the con-
struction of a maximal set of independent vertices through a simple greedy algorithm.
In pseudocode, the algorithm is as follows.
=
// Given a set s of vertices, compute a maximal set of independent vertices
Set IndependentSet(Set s)
{
// Initialize i to the empty set
Set i = EmptySet();
// Loop over all vertices in the input set
for (all vertices v in s) {
// If unmarked and has 8 or fewer neighboring vertices...
if (!Marked(v) && Degree(v) <= 8) {
// Add v to the independent set and mark all of v's neighbors
i.Add(v);
s.MarkAllVerticesAdjacentToVertex(v);
}
}
return i;
}
The independent set is guaranteed to be a constant fractional size of the current set
of vertices, in turn guaranteeing a height of
O
(log
n
) for the DK hierarchy. Additionally,
during the hierarchy construction pointers are added to connect deleted features of
polyhedron
P
i
to new features of polyhedron
P
i
+
1
, and vice versa. These pointers help
facilitate efficient queries on the hierarchy.
Figure 9.5 illustrates the construction of the Dobkin-Kirkpatrick hierarchy for a
convex polygon
P
as specified by vertices
V
0
through
V
11
.
P
0
is set to be equivalent
to
P
.
P
1
is obtained from
P
0
by deleting, say, the vertices
V
1
,
V
3
,
V
5
,
V
7
,
V
9
, and
V
11
(which form a maximal independent set).
P
2
is similarly obtained from
P
1
by
deleting vertices
V
2
,
V
6
, and
V
10
. Because
P
2
is a 2-simplex (a triangle), the hierarchy
construction stops.
Given a DK hierarchy, many different queries can be answered in an efficient
manner. For example, the point on
P
closest to a query point
S
can be located through
a simple recursive procedure. As an illustration, consider the case of Figure 9.6.
