Three-dimensional alpha shapes
<|reference_start|>Three-dimensional alpha shapes: 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 $\Real^3$. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter $\alpha \in \Real$ 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.<|reference_end|>
@article{edelsbrunner1994three-dimensional,
    title={Three-dimensional alpha shapes},
    author={Herbert Edelsbrunner, Ernst M"ucke},
    journal={arXiv preprint arXiv:math/9410208},
    year={1994},
    number={LACES 52B-94-25},
    archivePrefix={arXiv},
    eprint={math/9410208},
    primaryClass={math.CO cs.CC math.MG}
}