DOC PREVIEW
Stanford CS 468 - Study Notes

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 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 13 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 13 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 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 outsideSt 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 insideSt ab.• ψ is a relaxed unfolding if it differs from ϕabonly insideSt 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

Stanford CS 468 - Study Notes

Documents in this Course
Load more
Download Study Notes
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 Study Notes 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 Study Notes 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?