THREE-DIMENSIONAL ALPHA SHAPES
                                   
        
        ABSTRACT.  Frequently, the data produced in scientific computing
        applications 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 paper introduces the
        formal notion of the family of alpha shapes of a finite point set in
        space.  An algorithm is presented that constructs the family of a set
        of size n in worst-case time O(n^2).  A robust implementation of the
        algorithm is discussed and several applications in the area of
        scientific computing are mentioned.

        (This is taken from the paper "Three-dimensional Alpha Shapes" by
        Herbert Edelsbrunner and Ernst P Mucke.  A copy is available as a
        techreport with the Department of Computer Science, University of
        Illinois at Urbana-Champaign, 1304 W Springfield Ave, Urbana,
        IL 61801, USA.)
        

Alpha shapes are a generalization of convex hulls. Given a finite
point set S and a real parameter alpha, the alpha shape of S is some
polytope which is not necessarily convex or even connected.  The set
of all real alphas leads to a whole family of alpha shapes capturing
the intuitive notion of "fine" versus "crude shapes" of a point set.

For alpha=infinity, the alpha shape is identical to the convex hull.
However, as alpha decreases, the alpha shape shrinks by gradually
developing concavities.  For some alphas, these concavities may join
to form tunnels, and even holes may appear.  Intuitively, this happens
whenever it is possible to place a ball of radius rho=alpha amidst S,
such that it does not contain any points of S.

The whole family of (positive) alpha-shapes of S can be represented by
one single triangulations: the (closest-point) Delaunay triangulation.

Possible application areas include modeling, mesh generation, and
shape recognition.
