Maximal admissible faces and asymptotic bounds for the normal surface solution space (Q2431613): Difference between revisions

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.