66 III ComplexesIII.4 Alpha ComplexesIn this section, we use a radius constraint to introduce a family of subcomplexesof the Delaunay complex. These complexes are similar to theˇCech complexesbut differ from them by having natural geometric realization.Union of balls. Let S be a finite set of points in Rdand r a non-negativereal number. For each p ∈ S we let Bp(r) = p + rBdbe the closed ball withcenter p and radius r. The union of these balls is the set of points at distanceat most r from at least one of the points in S,Union(r) = {x ∈ Rd| ∃p ∈ S with kx − pk ≤ r}.To decompose the union, we intersect each ball with the corresponding Voronoicell, Rp(r) = Bp(r) ∩ Vp. Since balls and Voronoi cells are convex, the Rp(r)are also convex. Any two of them are disjoint or overlap along a common pieceof their boundaries, and together the Rp(r) cover the entire union, as in FigureIII.15. The alpha complex is isomorphic to the nerve of this cover,Figure III.15: The union of disks is decomposed into convex regions by the Voronoicells. The corresponding alpha complex is superimposed.Alpha(r) = {σ ⊆ S |\p∈σRp(r) 6= ∅}.Since Rp(r) ⊆ Vp, the alpha complex is a subcomplex of the Delaunay complex.It follows that for a set S in general position we get a geometric realization byIII.4 Alpha Complexes 67taking convex hulls, as in Figure III.15. Furthermore, Rp(r) ⊆ Bp(r) which im-plies Alpha(r) ⊆ˇCech(r). Since the Rp(r) are closed and convex and togetherthey cover the union, the Nerve Theorem implies that Union(r) and Alpha(r)have the same homotopy type.Weighted alpha complexes. For many applications it is useful to permitballs with different sizes. An example of significant importance is the modelingof biomolecules, such as proteins, RNA, and DNA. Each atom is representedby a ball whose radius reflects the range of its van der Waals interactions andthus depends on the atom type. Let therefore S be a finite set of points p withreal weights wp. Same as in Section III.3, we think of p as a ball Bpwith centerp and radius rp=√wp. We again consider the union of the balls, which wedecompose into convex regions now using weighted Voronoi cells, Rp= Bp∩ Vp.This is illustrated in Figure III.16. In complete analogy to the unweighted caseFigure III.16: Convex decomposition of a union of disks and the weighted alphacomplex superimposed.the weighted alpha complex of S is defined to be isomorphic to the nerve of theregions Rp, that is, the set of simplices σ ⊆ S such thatTp∈σRp6= ∅. Theweighted alpha complex is a subcomplex of the weighted Delaunay complexwhich is isomorphic to the nerve of the collection of weighted Voronoi cells.We need S to be in general position to guarantee that taking convex hullsof input points gives a geometric realization. Since the points are weighted,the notion of general position is slightly different from the unweighted case.In particular, it needs to imply that d + 2 or more Voronoi cells have no non-68 III Complexesempty common intersection. To see what this means let x ∈ Rdbe a pointin the common intersection of the weighted Voronoi cells Vpwith p ∈ σ. Bydefinition, the weighted square distances from x to the points are all the same.It follows there is a weight w ∈ R such that w = kx −pk − r2pfor all p ∈ σ.If x is outside the balls Bpthen this weight is positive and the sphere withcenter x and radius r =√w is well defined. It is orthogonal to the balls Bpin the sense that kx − pk2= r2p+ r2for all p ∈ σ. The same formula workseven if p lies on the boundary or in the interiors of the balls, except that theweight w is then zero or negative. We say a finite set of weighted points is ingeneral position if there is no point x with equal weighted square distance tod + 2 or more of the points. Equivalently, no d + 2 of the balls are orthogonalto a common (possibly imaginary) d-sphere.Filtration. Given a finite set S ⊆ Rd, we can continuously increase theradius and thus get a 1-parameter family of nested unions. Correspondingly,we get a 1-parameter family of nested alpha complexes. Because they are allsubcomplexes of the Delaunay complex, which is finite, only finitely many ofthe alpha complexes are different. Writing Kifor the i-th alpha complex inthe sequence, we get∅ = K0⊂ K1⊂ . . . ⊂ Km,which we call a filtration of Km= Delaunay. It is a stepwise construction ofthe final complex in such a way that every set along the way is a complex.The construction of a filtration is straightforward in the unweighted case andcan be extended to the weighted case as follows. Let p be a point with weightwp. For each r ∈ R we let Bp(r) be the ball with center p and radiuspwp+ r2and denote the corresponding alpha complex by Alpha(r). The collection ofsuch balls, interpreted as weighted points, defines the same weighted Voronoidiagram for any choice of r. It follows that every weighted alpha complexis a subcomplex of the same weighted Delaunay complex. Furthermore, theballs are nested, Bp(r0) ⊆ Bp(r) for r0≤ r, so the weighted alpha complexesare nested and define a filtration of the weighted Delaunay complex. We areinterested in the difference between two contiguous complexes in the filtration,Ki+1−Ki. We will see shortly that generically this difference is either a singlesimplex or a collection that forms an anticollapse.Collapses. Let K be a simplicial complex. It is convenient to call a simplexin the star a coface. A simplex in K is free if it has a unique proper coface.The star of a free simplex thus contains exactly two simplices, namely thesimplex itself and the unique proper coface. An elementary collapse is theIII.4 Alpha Complexes 69operation that removes a free simplex together with its unique proper coface.An elementary anticollapse is the inverse of that operation. If the free simplexis τ with dimension k = dim τ then the unique proper coface σ has dimensionk + 1 = dim σ and the elementary collapse that removes τ and σ is calleda (k, k + 1)-collapse. Each elementary collapse corresponds to a deformationretraction of the underlying space, which implies that it does not change thehomotopy type. Consider the special case in which K is the set of faces of ad-simplex. As illustrated in Figure III.17, this d-simplex can be reduced to asingle vertex by a sequence of 2d−1−1 elementary collapses. Starting with 2d−1faces, each elementary collapse removes two, leaving 2d− 1 − 2(2d−1− 1) = 1face, which is
View Full Document