DOC PREVIEW
Duke CPS 296.1 - Alpha Complexes

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Duke CPS 296.1 - Alpha Complexes

Documents in this Course
Lecture

Lecture

18 pages

Lecture

Lecture

6 pages

Lecture

Lecture

13 pages

Lecture

Lecture

5 pages

Load more
Download Alpha Complexes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Alpha Complexes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Alpha Complexes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?