2010/04/30 by Benjamin A. Burton · 7 citations
Computer Science · Mathematics · #Bijection #Bottleneck #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Dimension (graph theory) #Discrete mathematics #Enumeration #Geometric and Algebraic Topology #Geometry #Mathematics #Polytope #Quadrilateral #Regular polygon #Surface (topology) #Topological and Geometric Data Analysis #math.CO #math.GT #msc:52B05 #msc:57N10 #msc:57Q35
paper · pdf · doi:10.1016/j.jcta.2010.12.011
published in Journal of Combinatorial Theory Series A 118(4), 1410-1435 (Elsevier BV) · 31 pages, 10 figures, 2 tables; v2: minor revisions (to appear in Journal of Combinatorial Theory A)
arxiv created 2010/12/09 · openalex publication_date 2011/01/20 · arxiv updated 2011/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.