Optimizing the double description method for normal surface enumeration

DOI10.1090/S0025-5718-09-02282-0zbMath1246.57038arXiv0808.4050OpenAlexW3098139231MaRDI QIDQ3584785

Benjamin A. Burton

Publication date: 30 August 2010

Published in: Mathematics of Computation (Search for Journal in Brave)

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

zbMATH Keywords

normal surfacesvertex enumerationdouble description method

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Embeddings and immersions in topological manifolds (57N35) Triangulating manifolds (57Q15)

Related Items

Quadrilateral–Octagon Coordinates for Almost Normal Surfaces ⋮ The computational complexity of classical knot recognition ⋮ Maximal admissible faces and asymptotic bounds for the normal surface solution space ⋮ A tree traversal algorithm for decision problems in knot theory and 3-manifold topology ⋮ Random veering triangulations are not geometric ⋮ Converting between quadrilateral and standard solution sets in normal surface theory ⋮ The Weber-Seifert dodecahedral space is non-Haken

Uses Software

• Regina
• SnapPea
• FXrays

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Über das Homöomorphieproblem der 3-Mannigfaltigkeiten. I
• An algorithm to decide if a 3-manifold is a Haken manifold
• Normal surfaces in topologically finite 3-manifolds
• Ein Verfahren zur Aufspaltung einer 3-Mannigfaltigkeit in irreduzible 3- Mannigfaltigkeiten
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Normal surface \(Q\)-theory
• How good are convex hull algorithms?
• 0-efficient triangulations of 3-manifolds
• Thin position and the recognition problem for \(S^ 3\)
• Algorithms for the complete decomposition of a closed \(3\)-manifold
• Enumeration of non-orientable 3-manifolds using face-pairing graphs and union-find
• The computational complexity of knot and link problems
• The Complexity of Vertex Enumeration Methods
• Minimal triangulations for an infinite family of lens spaces
• A census of cusped hyperbolic 3-manifolds
• Symmetries, Isometries and Length Spectra of Closed Hyperbolic Three-Manifolds
• Introducing Regina, The 3-Manifold Topology Software
• The maximum numbers of faces of a convex polytope
• Generating all vertices of a polyhedron is hard