Abstract. Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is often useful or required to compute what one might call the `shape' of the set. For that purpose, this thesis deals with the formal notion of the family of alpha shapes of a finite point set in three-dimensional space. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a real parameter controlling the desired level of detail. Algorithms and data structures are presented that construct and store the entire family of shapes, with a quadratic time and space complexity, in the worst case.

Implementations of the algorithms are discussed, with an emphasis on the robust construction of three-dimensional Delaunay triangulations. A general-purpose programming technique, called Simulation of Simplicity, is used to cope with degenerate input data. This method relieves the programmer from the task of providing a consistent treatment for every single special case that can occur. The programs that use the technique tend to be considerably smaller and more robust than others.

Postscript [1536k]

Suggested BIBTeX entry:

@phdthesis{LABEL
,author=        "M{\"u}cke, E. P."
,title=         "Shapes and Implementations in Three-Dimensional Geometry"
,school=        "Department of Computer Science,
                University of Illinois at Urbana-Champaign"
,address=       "Ubana, Illinois"
,year=          1993
,url=           "ftp://ftp.cs.uiuc.edu/pub/dept/tech_reports/1993/UIUCDCS-R-93-1836.ps.gz"
}