August 2, 2004

BACK

Publications in Comp. Geom. & Graphics on Voronoi Diagrams & related concepts, as well as their applications by:

• The union of balls and its dual shape, 1995.
• Three-dimensional alpha shapes, 1994.
• Delaunay and Regular Triangulation in Space, 1993.
• On the shape of a set of points in the plane, 1983.

BibTeX references.

Web links:

• Alpha Shapes: Definition and Software.
• Raindrop Geomagic, Inc. : www.geomagic.com:
  • Company co-founder
• References in Computational Topology (link).
• References in Computational Chemistry (link).

Web links:

• ACM portal

Efficient algorithms are described for computing topological, combinatorial, and metric properties of the union of finitely many balls in R^d . These algorithms are based on a simplicial complex dual to a certain decomposition of the union of balls, and on short inclusion-exclusion formulas derived from this complex. The algorithms are most relevant in R³ where unions of finitely many balls are commonly used as models of molecules.

Keywords: power diagram.

Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the "shape" of the set. For that purpose, this article introduces the formal notion of the family of alpha-shapes of a finite point set in IR^3. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter alpha in IR controlling the desired level of detail. An algorithm is presented that constructs the entire family of shapes for a given set of size n in time 0(n^2), worst case. A robust implementation of the algorithm is discussed, and several applications in the area of scientific computing are mentioned.

Keywords: Delaunay triangulations, computational graphics, geometric algorithms, point sets, polytopes, robust implementation, scientific computing, scientific visualization, simplicial complexes, simulated perturbation, three-dimensional space.

Introduction

Goal of paper: offer a concrete and formal definition of "shape" (of point sets in IR^3).

Generalization of the concept of convex-hull:

• alpha --> infinity : shape == convex hull of point set
• alpha --> 0 : shape shrinks gradually developing cavities which may form tunnels and holes.

A piece of the polytope - the generalization of polygons and polyhedra to IR^n - disappears when alpha becomes small enough so that a sphere with radius alpha, or several such spheres, can occupy its space without enclosing any of the points of the point set S - NB: similar to the empty circumsphere criterion of Delaunay.

Assumptions/Restrictions:

1. Straighten the "surface" of the resulting object: circular edges & spherical caps --> straight line segments & triangular patches.
    
2. General position of the point set: no 4 points are co-planar, no 5 points are co-spherical - a small simulated perturbation permits to enure this condition to avoid degeneracies.
    
3. The smallest sphere through any 2, 3 or 4 points has a radius different than alpha.
    

Related Geometric Concepts

* Alpha Hulls and Alpha Diagrams

In chemistry and biology, alpha-diagrams are known as "space-filling diagrams": the union of all alpha-balls centered on points of S. The boundary of such diagrmas is mad of spherical caps, circular arcs and vertices. They are not restricted to equally large balls. The latter can be modeled with weighted alpha-shapes and diagrams.

* Delaunay Triangulations and Voronoi Diagrams

The Delaunay triangulation, D, includes the union of all alpha-shapes, S_alpha, i.e., all edges and triangles of S_alpha (0 < alpha < infinity) are in D.

* Alpha Complexes

* Extensions

Negative Alpha Values

Sub-complexes of the "furthest-point" Delaunay triangulation of S.

Weighted Points

A (real-valued) weight is associated to each point of S. This weight is used to set the ball radius (alpha). NB: If all points have the same weight, we are back to the Delaunay triangulation of the points.

Higher Dimensions

Directly extensible, but the worst-case complexity grows exponentially (in number of faces of S_alpha).

Combinatorial Analysis

S has at most 2n^2-5n different alpha-shapes <-- upper-bound (too pessimistic, see text).

Algorithms

Based on local transformations or "flips".

Geometric tests: on which side of a plane or sphere a fourth, resp. fifth, point lies. Formula for these two tests are given in terms of determinants. Similar formula are also given to comput the smallest radius of the circumsphere to an edge (2 points), a triangle or a tetrahedron.

Geometric tests for deficiding if an edge or triangle is attached or not are also given in terms of determinants.

Implementations

1. Delaunay triangulations using flips.
2. alpha-intervals computation for all simplices in a Delaunau triangulation, followed by sorting of the endpoints of these intervals.
3. alpha-shape visualizer with user-defined alpha (parameter).

Data Structures

Triangle-edge structure, interval tree or linear array.

Simulated Perturbation

Simulation of Simplicity (SoS) perturbs the data slightly so that all degeneracies disappear.

Applications and Further Illustrations

Automatic mesh generation and geometric modeling.

Molecular structures and protein folding analysis.

Distribution of point sets, e.g., galaxies on the universe.

Open Problems

Improving running time.

Maitaining Alpha Shapes.

Features and signatures:

• Computing volumes (easy).
• Computing connectivity (difficult).
• Computing signatures: evolution of the number of components as alpha varies (alpha-spectrum).
• Study the relations with fractal dimension.

Available software

Alvis - a 3d ALpha shape VISualizer -

•    ftp://ftp.ncsa.uiuc.edu/Visualization/Alpha-shape/   

[ TOP ]

Notes from a lecture given in July 1993.

Compressed (gzip) postscript file: click here.

Lecture by Herbert Edelsbrunner, transcribed by Pedro Ramos and Saugata Basu. The regular triangulation has been popularized by Herbert as the appropriate generalization of the Delaunay triangulation to collections of disks. This talk was mostly devoted to definitions of Voronoi cells, nerves, simplicial complexes, Delaunay triangulations, circular inversions, stereographic projections, and their applications to computational geometry.

Mathematical definition of Alpha shapes in 2D.

BACK        TOP    

Page created & maintained by Frederic Leymarie, 2000-4.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu