next up previous
Next: Signatures Up: Alpha Shapes: Definition and Previous: Complex and Shape

Filter and Filtration


Suppose we grow all balls simultaneously without changing Voronoi cells. In this case, all cells of the decomposition C of can only grow, and the dual complex can only get larger. The result is a one-parametric family of simplicial complexes.

More formally, let , , and . For the radius of is its weight, and for the radius is . By construction, the Voronoi cell of in is the same as the Voronoi cell of in B. The -complex, , is the dual complex of . The -shape is . By monotonicity of the cells , we have

whenever . For sufficiently large , geometrically realizes the nerve of the collection of Voronoi cells. We refer to this complex as the (weighted) Delaunay simplicial complex or (weighted) Delaunay triangulation of B, and denote this by . All are subcomplexes of .

Since is a finite complex, there are only finitely many subcomplexes, and the ones we are interested in are naturally ordered by inclusion. We index the complexes from 0 through , and define as the r-th complex after the trivial complex, . The last complex is .

The linear structure is essential in obtaining algorithms that efficiently deal with the entire family of alpha complexes and shapes. As a consequence, the most important step in the computation is the construction of . Many efficient algorithms have been described in the literature. The implementation provided as part of our software distribution builds incrementally, adding each point by a sequence of flips [9]. The points are added in random order.

The linear sequence of alpha complexes can be understood as assembling one simplex at a time. This is not quite correct because and may differ by more than only one simplex. In such a case, we can add the simplices in one by one, lower dimensions first. The resulting sequence of simplices,

is called a filter, and the sequence of complexes,

, is a filtration. For each , t here is a and an with .

next up previous
Next: Signatures Up: Alpha Shapes: Definition and Previous: Complex and Shape

<> 11-Sep-95