Embeddability in the 3 sphere is decidable Conference Paper


Author(s): Matoušek, Jiří; Sedgwick, Eric; Tancer, Martin; Wagner, Uli
Title: Embeddability in the 3 sphere is decidable
Affiliation IST Austria
Abstract: We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in ℝ3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, then there is also an embedding in which X has a short meridian, i.e., an essential curve in the boundary of X bounding a disk in S3 nX with length bounded by a computable function of the number of tetrahedra of X.
Keywords: Simplicial complex; 3-manifold; Embedding
Conference Title: SoCG: Symposium on Computational Geometry
Conference Dates: June 8-11, 2014
Conference Location: Kyoto, Japan
ISBN: 978-1-4503-2594-3
Publisher: ACM  
Date Published: 2014-06-01
Start Page: 78
End Page: 84
Sponsor: ERC Advanced Grant No. 267165; Grant GRADR Eurogiga GIG/11/E023 (SNSF-PP00P2-138948); Swiss National Science Foundation (SNSF-200020-138230)
URL:
DOI: 10.1145/2582112.2582137
Notes: We thank David Bachman, Ryan Derby-Talbot, and William Jaco for very helpful conversations. We further thank Tony Huynh for kind answers to our questions, Helena Nyklova ́ for help with many pictures, Isaac Mabillard for remarks on a preliminary write-up of the algorithm for EMBED3→3, and an anonymous reviewer for useful comments.
Open access: yes (repository)
IST Austria Authors
  1. Uli Wagner
    50 Wagner
  2. Martin Tancer
    9 Tancer
Related IST Austria Work