Optimizing the double description method for normal surface enumeration

DOI10.1090/S0025-5718-09-02282-0zbMATH Open1246.57038arXiv0808.4050OpenAlexW3098139231MaRDI QIDQ3584785FDOQ3584785

Authors: Benjamin A. Burton 

Publication date: 30 August 2010

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

Abstract: Many key algorithms in 3-manifold topology involve the enumeration of normal surfaces, which is based upon the double description method for finding the vertices of a convex polytope. Typically we are only interested in a small subset of these vertices, thus opening the way for substantial optimization. Here we give an account of the vertex enumeration problem as it applies to normal surfaces, and present new optimizations that yield strong improvements in both running time and memory consumption. The resulting algorithms are tested using the freely available software package Regina.

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

Recommendations

• Converting between quadrilateral and standard solution sets in normal surface theory
• The complexity of the normal surface solution space
• Computational topology with Regina: algorithms, heuristics and implementations

zbMATH Keywords

vertex enumerationdouble description methodnormal surfaces

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Computational topology with Regina: algorithms, heuristics and implementations
• The Weber-Seifert dodecahedral space is non-Haken
• The complexity of the normal surface solution space
• Random veering triangulations are not geometric
• Converting between quadrilateral and standard solution sets in normal surface theory
• 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

Uses Software

• Regina
• SnapPea
• FXrays

This page was built for publication: Optimizing the double description method for normal surface enumeration

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