2014/02/04 by Jiřı́ Matoušek, Jiří Matoušek, Matoušek, Jiří +6
Computer Science · Mathematics · #05E45 #57N10 (57M27 #57Q35 #68U05 #68W99) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Geometric Topology (math.GT) #Geometric and Algebraic Topology #Homotopy and Cohomology in Algebraic Topology #Topological and Geometric Data Analysis #cs.CG #math.GT #msc:05E45 #msc:57N10 #msc:57Q35 #msc:68U05
paper · pdf · doi:10.48550/arxiv.1402.0815
54 pages, 26 figures; few faulty references to figures in the first version fixed
openalex publication_date 2014/02/04 · arxiv created 2014/02/05 · arxiv updated 2014/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 R3? 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∖ X with length bounded by a computable function of the number of tetrahedra of X.