Maximal admissible faces and asymptotic bounds for the normal surface solution space

DOI10.1016/J.JCTA.2010.12.011MaRDI QIDQ2431613zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Benjamin A. Burton

Publication date 15 April 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.2605

zbMATH Keywords

3-manifoldscomplexityface latticenormal surfacespolytopes

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to manifolds and cell complexes (57-04) Topological manifolds (57N99) Triangulating manifolds (57Q15)

Abstract: The enumeration of normal surfaces is a key bottleneck in computational three-dimensional topology. The underlying procedure is the enumeration of admissible vertices of a high-dimensional polytope, where admissibility is a powerful but non-linear and non-convex constraint. The main results of this paper are significant improvements upon the best known asymptotic bounds on the number of admissible vertices, using polytopes in both the standard normal surface coordinate system and the streamlined quadrilateral coordinate system. To achieve these results we examine the layout of admissible points within these polytopes. We show that these points correspond to well-behaved substructures of the face lattice, and we study properties of the corresponding "admissible faces". Key lemmata include upper bounds on the number of maximal admissible faces of each dimension, and a bijection between the maximal admissible faces in the two coordinate systems mentioned above.

Review text

The present paper deals with the use of normal surface theory in 3-dimensional computational topology: see \textit{H. Kneser}'s foundational paper [``Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten, Jahresbericht D. M. V. 38, 248--260 (1929; JFM 55.0311.03)], together with the developments by Haken and Jaco-Oertel [\textit{W. Haken}, ``Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten, Acta Math. 105, 245--375 (1961; Zbl 0100.19402), ``Über das Homöomorphieproblem der 3-Mannigfaltigkeiten. I, Math. Z. 80, 89--120 (1962; Zbl 0106.16605), \textit{W. Jaco} and \textit{U. Oertel}, ``An algorithm to decide if a 3-manifold is a Haken manifold, Topology 23, 195-209 (1984; Zbl 0545.57003)]. In particular, the author faces the crucial problem of enumerating normal surfaces in a given (triangulated) 3-manifold, via the underlying procedure of enumerating admissible vertices of a high-dimensional polytope (admissibility being a powerful but non-linear and non-convex constraint). The main results of the present paper are significant improvements upon the best known asymptotic bounds on the number of admissible vertices (see [\textit{J. Hass, J. C. Lagarias} and \textit{N. Pippenger}, [``The computational complexity of knot and link problems, J. ACM 46, No. 2, 185--211 (1999; Zbl 1065.68667)], [\textit{B. A. Burton}, ``The complexity of the normal surface solution space, in: SCG'10: Proceedings of the Twenty-Sixth Annual Symposium on Computational Geometry, ACM Press, pp. 201--209 (2010) and ``Optimizing the double description method for normal surface enumeration, Math. Comput. 79, No. 269, 453--484 (2010; Zbl 1246.57038)]). To achieve these results, the author examines the layout of admissible points within polytopes in both the standard normal surface coordinate system and the streamlined quadrilateral coordinate system. These points are proved to correspond to well-behaved substructures of the face lattice, and the properties of the corresponding ``admissible faces are studied. Key lemmata include upper bounds on the number of maximal admissible faces of each dimension, and a bijection between the maximal admissible faces in the two coordinate systems mentioned above.

Recommendations

• The complexity of the normal surface solution space
• Computational topology and normal surfaces: theoretical and experimental complexity bounds
• Converting between quadrilateral and standard solution sets in normal surface theory
• Quadrilateral–Octagon Coordinates for Almost Normal Surfaces
• The Thurston norm via normal surfaces

Cites work

• 0-efficient triangulations of 3-manifolds
• 3-manifold knot genus is NP-complete
• A census of cusped hyperbolic 3-manifolds
• A new decomposition theorem for 3-manifolds
• Algorithms for the complete decomposition of a closed 3-manifold
• An algorithm to decide if a 3-manifold is a Haken manifold
• Complexity theory of three-dimensional manifolds
• Converting between quadrilateral and standard solution sets in normal surface theory
• FACE PAIRING GRAPHS AND 3-MANIFOLD ENUMERATION
• Generating all vertices of a polyhedron is hard
• scientific article; zbMATH DE number 3538541 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 2008526 (Why is no real title available?)
• scientific article; zbMATH DE number 849995 (Why is no real title available?)
• scientific article; zbMATH DE number 2227022 (Why is no real title available?)
• Lectures on Polytopes
• Normal surface Q-theory
• Normal surfaces in topologically finite 3-manifolds
• Optimizing the double description method for normal surface enumeration
• Quadrilateral–Octagon Coordinates for Almost Normal Surfaces
• The complexity of the normal surface solution space
• The Complexity of Vertex Enumeration Methods
• The computational complexity of knot and link problems
• The maximum numbers of faces of a convex polytope
• The Weber-Seifert dodecahedral space is non-Haken
• Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
• Thin position and the recognition problem for \(S^ 3\)
• Über das Homöomorphieproblem der 3-Mannigfaltigkeiten. I

Cited in

(2)

• Computational topology and normal surfaces: theoretical and experimental complexity bounds
• The complexity of the normal surface solution space

Describes a project that uses

Uses Software

• SnapPea

This page was built for publication: Maximal admissible faces and asymptotic bounds for the normal surface solution space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431613)