@article{4037, 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 article introduces the formal notion of the family of alpha-shapes of a finite point set in R3. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter alpha is-an-element-of 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(n2), worst case. A robust implementation of the algorithm is discussed, and several applications in the area of scientific computing are mentioned.}, author = {Edelsbrunner, Herbert and Mücke, Ernst}, journal = {ACM Transactions on Graphics}, number = {1}, pages = {43 -- 72}, publisher = {ACM}, title = {{Three-dimensional alpha shapes}}, doi = {10.1145/174462.156635}, volume = {13}, year = {1994}, }