Abstract. 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 paper introduces the formal notion of the family of alpha-shapes of a finite point set in R^3. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter alpha in R 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 O(n^2), worst case. A robust implementation of the algorithm is discussed and several applications in the area of scientific computing are mentioned.

Postscript [104k]
(very) low-quality B&W Postscript [230k] of the journal publication's color plates

See also: ACM citation page including review.

Suggested BIBTeX entry:

@article{edels:3d-alpha
,author=        "Edelsbrunner, H. and M{\"u}cke, E. P."
,title=         "Three-dimensional Alpha Shapes"
,journal=       "ACM Transactions on Graphics"
,volume=        13
,number=        1
,year=          1994
,pages=         "43--72"
,url=           "http://www.geom.umn.edu/locate/cglist/GeomDir/shapes94.html"
}