Embeddability in the 3-Sphere is decidable

J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Journal of the ACM 65 (2018) 5.


Journal Article | Published | English

Scopus indexed
Author
Matoušek, Jiří; Sedgwick, Eric; Tancer, MartinIST Austria ; Wagner, UliIST Austria
Department
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 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, that is, 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.
Publishing Year
Date Published
2018-01-01
Journal Title
Journal of the ACM
Volume
65
Issue
1
Article Number
5
IST-REx-ID
425

Cite this

Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3-Sphere is decidable. Journal of the ACM. 2018;65(1):5. doi:10.1145/3078632
Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2018). Embeddability in the 3-Sphere is decidable. Journal of the ACM, 65(1), 5. https://doi.org/10.1145/3078632
Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability in the 3-Sphere Is Decidable.” Journal of the ACM 65, no. 1 (2018): 5. https://doi.org/10.1145/3078632.
J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the 3-Sphere is decidable,” Journal of the ACM, vol. 65, no. 1, p. 5, 2018.
Matoušek J, Sedgwick E, Tancer M, Wagner U. 2018. Embeddability in the 3-Sphere is decidable. Journal of the ACM. 65(1), 5.
Matoušek, Jiří, et al. “Embeddability in the 3-Sphere Is Decidable.” Journal of the ACM, vol. 65, no. 1, ACM, 2018, p. 5, doi:10.1145/3078632.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Earlier Version

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1402.0815

Search this title in

Google Scholar