Introduction
The  -shape
of a finite point set S is a polytope that is uniquely determined
by S and a parameter .
It expresses the intuitive notion of the "shape'' of S, and
controls the level of detail reflected by the polytope. The original
paper on -shapes
[14] defines the concept in the plane.
An extension to three dimension together with an implementation is
reported in [3]. In both papers the relationship
between -shapes
and Delaunay triangulations [13] is described
in detail and used as the basis of an algorithm for constructing alpha
shapes.
A question that was repeatedly asked in the past is whether it is
possible to construct a shape that represents different levels of
detail in different parts of space. This is indeed possible by assigning
a weight to each point. Intuitively, a large weight favors and a small
weight discourages connections to neighboring points. We refer to
the resulting concept as the weighted alpha shape. If all
weights are zero, it is the same as the original, unweighted alpha
shape. This document makes no distinction between weighted and unweighted
alpha shapes, unless such a distinction is important. What are the
applications where weights can be beneficial?
| (i) |
A common computational task in biology is modeling
molecular structures. It is natural to use -shapes
for this purpose as they are precise duals of the popular sphere
models obtained by taking unions of balls, see e.g. [15].
The weights are the radii (e.g. van der Waals radii) of the
atoms. |
| (ii) |
In reconstructing a surface from scattered
point data, it is rarely the case that the points are uniformly
dense everywhere on the (unknown) surface. The assignment of
large weights in sparse regions and of small weights in dense
regions can be used to counteract the effects resulting from
uneven density distributions. |
| (iii) |
Another goal that can be achieved by assigning
weights is to enforce certain edges or faces. These might be
given as part of the input, but they cannot be processed directly
since alpha shapes are defined only for finite point sets and
not for other geometric objects. |
| It seems that weighted alpha shapes
are a perfect solution to problem (i), while they are but a
heuristic approach to problems (ii) and (iii). |
|
Complex
and Shape
Up front two remarks to avoid any confusion and misconceptions.
First, it is more cumbersome to distinguish between d=2 and d=3
dimensions than to phrase all definitions in d-dimensional Euclidean
space, for some arbitrary but fixed positive integer d. Second,
we use real numbers as weights. If we think in terms of spheres,
we may think of radii, which are the square roots of the weights.
In this theory, it is possible that a point has negative weight
so the corresponding sphere has imaginary radius.
A point p with weight w(p) is interpreted as the sphere
with center p and square radius w(p). We denote the corresponding
ball by b(p); it consists of all points on and inside the sphere.
All points with negative weight correspond to
empty balls.
|
Figure 1:
The union of a set of disks in the plane. |
The shape of a finite set of
weighted points is defined in terms of a decomposition of the union
of corresponding balls into convex sets. This decomposition is defined
by the (weighted) Voronoi cells of the balls. Specifically, the
Voronoi cell v(p) of b(p) is the set of all points whose power from
b(p) is no larger than from any other ball, where the power is the
square distance from the center of b(p) minus the squar radius of
b(p).
|
Figure 2: The decomposition of the union
of disks defind by their Voronoi cells.
|
It is a convex polyhedron, and
its intersection with the ball union
is convex. The convex cells have pairwise disjoint interiors, but
some of them overlap along common boundary pieces. These pieces
of overlap are instrumental in the construction of a set system
closed under the subset operation. In topology, such a system is
referred to as an abstract simplicial complex. Specifically,
we define the nerve of the collection C of cells b(p) n
V(p) as the set of subsets of C that have non-empty common intersections.
Assuming general position of the
points or balls, the largest set in the nerve is of size d+1, i.e.,
a triple in the plane and a quadruple in three dimensions. Under
this assumption, the nerve has a natural geometric realization by
mapping each cell b(p) n V(p) in C to the point p. A set in the
nerve maps to the convex hull of the points that correspond to the
elements in the set. This realization is a (geometric) simplicial
complex.
|
Figure 3: The dual complex of the disk union.
|
We refer to this complex as the
dual complex of the collection of weighted points. The
set of points covered by simplices in the complex is sometimes refered
to as the underlying space of the complex; in this context we also
call it the dual shape of the collection of weighted points.
|
Figure 4: The decomposition of the union
of disks and its dual complex overlapped.
|
Among the most useful properties of dual complex are the homotopy
equivalence between its underlying space and the union of corresponding
balls, as well as that this union can be expressed as the alternating
sum of common ball intersections, with one term per simplex in the
dual complex. This implies short inclusion-exclusion formulas for
the d-dimensional volume and other measures of the union of balls.
|
Filter
and Filtration
Suppose we grow all balls b(p) simultaneously without changing Voronoi
cells. In this case, all cells of the convex decomposition of the
union can only grow, and the dual complex can only get larger. The
result is a one-parametric family of simplicial complexes. To describe
this idea more formally, we introduce a time parameter f, which
is a real number that goes from minus to plus infinity. At time
t, the ball b(p) grows to square radius w(p)+t; it still has the
same center, namely p. At time t=0, we have the original collection
of balls. By construction, the Voronoi cells are the same at all
times, but the union gradually grows, all the way from the empty
set of time t = -00 to the entire space at t = +00. By definition,
the -complex is
the dual complex at time t =  .
Since the cells decomposing the union of balls can only grow with
time, it follows that the alpha complex can only grow with time.
For sufficiently large t, the -complex
is the dual of the entire Voronoi diagram, which is also known as
the Delaunay triangulation of the weighted points. Between the empty
complex and the Delaunay triangulation, we have a finite collection
of alpha complexes naturally ordered by inclusion. We refer to this
ordering of complexes as a filtration. We represent the filtration
implicitly by the sequence of simplices ordered by the time they
enter the alpha complex. |
Signatures
The filter of Del B implicitly represents all alpha complexes defined
by B as prefixes. The availability of this simplex sequence favors
incremental algorithms for computing properties of alpha shapes. The
software considers metric properties:
-
- volume, area, and length (defined below),
combinatorial properties:
-
- number of tetrahedra, triangles, edges, and vertices, distinguishing
between simplices on the boundary and in the interior,
and topological properties:
-
- number of components, independent tunnels, and voids, as expressed
by the three betti numbers.
As shown in every additive and continuous map from the set of convex
bodies to  invariant
under rigid motion is a linear combination of quermassintegrals.
In  , the quermassintegrals
are basically volume, area, mean width, and the Euler number. Length
is defined as an extension of the mean width to non-convex bodies.
Specifically, length is the sum of edge lengths, each weighted
by the (possibly negative) complementary angle. The Euler number
is the alternating sum of betti numbers.
Each property defines a signature f:[n]  R
, where n = {1,2, ...n}. Signatures are useful in studying shapes
and convenient in quickly identifying the "interesting'' ones
in the typically huge family of alpha shapes.
The signatures expressing the above metric and combinatorial properties
are straightforward to compute: scan the filter from 0 through n
and increment or decrement the current value depending on the next
simplex. Such a strategy also works for the three betti numbers,
but is less obvious. |
Data
Structures
The main two data structures built and used by our software are the
Delaunay triangulations and a sequence of simplices so that each alpha
complex is a prefix of that sequence. The sequence is accessible through
a linear list and an interval tree. The list supports the computation
of signatures, and the tree provides fast access to individual shapes.
We restrict the discussion to d = 3 dimensions.
In three dimensions, the Delaunay triangulation is represented by
a triangle-based pointer structure [16].
Each triangle is stored with a pointer each to the six neighboring
triangles sharing an edge. Following appropriate pointers, each in
constant time, it is possible to traverse the triangles around a given
edge, or the triangles opposite a given vertex, or all triangles on
the convex hull boundary. Further details can be found in [8].
An important ingredient in the construction of the Delaunay triangulation,
which is synonymous to constructing its triangle-based pointer structure,
is the use of exact arithmetic and symbolic computation. The input
coordinates and radii are restricted to be integers of fixed-point
reals. (A negative radius, -R, is interpreted as R times the imaginary
unit.)
All geometric tests are performed in exact arithmetic so that degenerate
cases can be identified without ambiguity. Such degeneracies include
four points on a common plane, and five balls with common orthogonal
sphere.
All possible degeneracies are reduced to the general case by the use
of a simulated perturbation [1]. In the
presence of coplanar points on the boundary of the convex hull boundary,
the perturbation results in the construction of infinitesimally thin
tetrahedra. As a fortunate consequence of the perturbation scheme,
no such flat tetrahedra exist in the interior of the convex hull.
We can therefore remove the flat tetrahedra on the outside without
violating the face-to-face property of the complex. |
|
