Processing...

### Three-dimensional alpha shapes

**1994-10-12**

9410208 | math.CO

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.

**Login to like/save this paper, take notes and configure your recommendations**