About the Book

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

The concept of alpha shapes formalizes the intuitive notion of "shape'' for spatial point set data, which occurs frequently in the computational sciences. An alpha shape is a concrete geometric object that is uniquely defined for a particular point set. It thus stands in sharp contrast to many common concepts in computer graphics, such as isosurfaces, which are approximate by definition and the exact form depends on the algorithm used to construct them.

Alpha shapes are generalizations of the convex hull. Given a finite point set S, and a real parameter alpha, the alpha shape of S is a polytope which is neither necessarily convex nor necessarily connected. The set of all real numbers alpha leads to a family of shapes capturing the intuitive notion of "crude'' versus "fine'' shape of a point set. For sufficiently large alpha, the alpha shape is identical to the convex hull of S. As alpha decreases, the shape shrinks and gradually develops cavities. These cavities may join to form tunnels and voids. For sufficiently small alpha, the alpha shape is empty.

The Stony Brook Algorithm Repository

BioGeometry Alpha Shapes

Problem Links