Topology Preserving Edge Contractions: What are theyand how do we find them?Jon McAlisterDecember 4, 20021Edge contractions• The contraction of an edge ab is a local transformation of K thatreplaces Stab = St a ∪ St b by the star of a new vertex, St c.a b c• What can go wrong?dabdc2Basic definitions• The closure of B ⊆ K is B = {τ ∈ K | τ ≤ σ ∈ B}.• The star of B ⊆ K is St B = {τ ∈ K | τ ≥ σ ∈ B}.• The link of B ⊆ K is Lk B =St B− St B.• An edge is contractable if its contraction does not change the surfacetopology.• A triangulation of a 2-manifold is irreducible if no edge iscontractible.• Two edge contractions in a 2-manifold are independent if they donot effect the same triangle. That is, Stab ∩ St cd = ∅.3Results overview• Topology Preserving Edge Contractions, by Dey, Edelsbrunner,Guha, and Nekhayev, 1999.– Results in characterization of topology preserving edgecontractions for simplicial complexes up to dimension 3 [1].• Hierarchy of Surface Models and Irreducible Triangulation, byCheng, Dey, and Poon, 2002.– Greedy algorithm to find Θ(n) independent topology preservingedge contractions in an orientable 2-manifold, each of whicheffect a small number of triangles [2].– Computing a topology preserving hierarchy of O(n + g2) size andO(log n + g) depth for an orientable 2-manifold [2].– Improved bound on the number of vertices in an irreducibletriangulation of an orientable 2-manifold [2].4Simplicial map• A vertex map for two complexes K and L is a map f : Vert K →Vert L.• The barycentric coordinates of a point x ∈ σ, σ ∈ K, are the uniquereals bu(x), u ∈ Vert K, so bu(x) 6= 0 only if u ≤ σ andx =Xu∈Vert Kbu(x)· u1 =Xu∈Vert Kbu(x)• The simplicial map φ : |K| → |L| for a vertex map f is defined byφ(x) =Xu∈Vert Kbu(x)· f(u)5Unfoldings• f : |K| → |L| is a simplicial homeomorphism iff f is bijective andf−1is also a vertex map.• An edge contraction of ab can then be defined as a surjectivesimplicial map ϕab: |K| → |L| defined by the surjective vertex mapf(u) =u if u ∈ Vert K − {a, b}c if u ∈ {a, b}• Note that outsideSt ab, ϕabis the identity, but inside it is noteven injective.• An unfolding of ϕabis a simplicial homeomorphism ψ : |K| → |L|.• ψ is a local unfolding if it differs from ϕabonly insideSt ab.• ψ is a relaxed unfolding if it differs from ϕabonly insideSt St ab.6Order and Boundary• The order of σ is the smallest integer i for which there is a (k − i)simplex η such that St σ and St η are combinatorially equivalent.Since the interior of η is homeomorphic to Rk−i, the star of σ ishomeomorphic to Rk−i× X, for some topological space X ofdimension i.21201• The j-th boundary of a simplicial complex K is the set of simpliceswith order no less than j:BdjK = {σ ∈ K | ord σ ≥ j}71-complexes• For each i we extend the i-th boundary by adding a dummy vertexω, and cones from ω to all simplices in the (i + 1)-st boundary:BdωiK = BdiK ∪ ω· Bdi+1K• For a simplex σ ∈ BdωiK, we denote the link within BdωiK as Lkωiσ.• For a 1-complex K, the following are equivalent:1. (i) Lkω0a ∩ Lkω0b = ∅.2. (ii) ϕabhas a local unfolding.3. (iii) ϕabhas an unfolding.a b a bww82-complexes• For a 2-complex K then the following statements are equivalent:1. (i)Lkω0a ∩ Lkω0b = Lkω0ab, andLkω1a ∩ Lkω1b = ∅2. (ii) ϕabhas a local unfolding.• They demonstrate a 2-complex which has neither a local nor arelaxed unfolding, but which does have an unfolding.• For a 2-manifold the following statements are equivalent:1. (i) Lk a ∩ Lk b = Lk ab.2. (ii) ϕabhas a local unfolding.3. (iii) ϕabhas an unfolding.9Steinitz’ Theorem (1922)• A convex 3-polytope is the convex hull of finitely many points in R3that do not all lie in a common plane.• The 1-skeleton is the subcomplex of all vertices and edges.• A graph G is planar if it is isomorphic to a 1-complex in R2.• A graph is 3-connected if the deletion of any two vertices togetherwith their edges leaves the graph connected.• Steinitz’ Theorem (1922): For every 3-connected planar graph thereis a convex 3-polytope with an isomorphic 1-skeleton.103-complexes• For a 3-complex K then the following statements are equivalent:1. (i)Lkω0a ∩ Lkω0b = Lkω0ab,Lkω1a ∩ Lkω1b = Lkω1ab, andLkω2a ∩ Lkω2b = ∅2. (ii) ϕabhas a relaxed unfolding.• For a 3-manifold the following statements are equivalent:1. (i) Lk a ∩ Lk b = Lk ab.2. (ii) ϕabhas a local unfolding.3. (iii) ϕabhas an unfolding.11Results overview• Topology Preserving Edge Contractions, by Dey, Edelsbrunner,Guha, and Nekhayev, 1999.– Results in characterization of topology preserving edgecontractions for simplicial complexes up to dimension 3 [1].• Hierarchy of Surface Models and Irreducible Triangulation, byCheng, Dey, and Poon, 2002.– Greedy algorithm to find Θ(n) independent topology preservingedge contractions in an orientable 2-manifold, each of whicheffect a small number of triangles [2].– Computing a topology preserving hierarchy of O(n + g2) size andO(log n + g) depth for an orientable 2-manifold [2].– Improved bound on the number of vertices in an irreducibletriangulation of an orientable 2-manifold [2].12References[1] Tamal K. Dey, Herbert Edelsbrunner, Sumanta Guha, and Dmitry V.Nekhayev. Topology preserving edge contractions. Publ. Inst. Math(Beograd) (N.S.), 66 (1999), 23-45, 1999.[2] Siu-Wing Cheng, Tamal K. Dey, and Sheung-Hung Poon. Hierarchyof surface models and irreducible triangulation. Available athttp://cs468.stanford.edu,
View Full Document