Earlier Version

# Embeddability in the 3 sphere is decidable

J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, in:, Proceedings of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 78–84.

Download (ext.)

*Conference Paper*|

*Published*|

*English*

Author

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 ℝ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.

Publishing Year

Date Published

2014-06-01

Proceedings Title

Proceedings of the Annual Symposium on Computational Geometry

Acknowledgement

ERC Advanced Grant No. 267165; Grant GRADR Eurogiga GIG/11/E023 (SNSF-PP00P2-138948); Swiss National Science Foundation (SNSF-200020-138230).

Page

78 - 84

Conference

SoCG: Symposium on Computational Geometry

Conference Location

Kyoto, Japan

Conference Date

2014-06-08 – 2014-06-11

IST-REx-ID

### Cite this

Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3 sphere is decidable. In:

*Proceedings of the Annual Symposium on Computational Geometry*. ACM; 2014:78-84. doi:10.1145/2582112.2582137Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2014). Embeddability in the 3 sphere is decidable. In

*Proceedings of the Annual Symposium on Computational Geometry*(pp. 78–84). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582137Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability in the 3 Sphere Is Decidable.” In

*Proceedings of the Annual Symposium on Computational Geometry*, 78–84. ACM, 2014. https://doi.org/10.1145/2582112.2582137.J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the 3 sphere is decidable,” in

*Proceedings of the Annual Symposium on Computational Geometry*, Kyoto, Japan, 2014, pp. 78–84.Matoušek J, Sedgwick E, Tancer M, Wagner U. 2014. Embeddability in the 3 sphere is decidable. Proceedings of the Annual Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry 78–84.

Matoušek, Jiří, et al. “Embeddability in the 3 Sphere Is Decidable.”

*Proceedings of the Annual Symposium on Computational Geometry*, ACM, 2014, pp. 78–84, doi:10.1145/2582112.2582137.**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

Open Access