Optimizing the double description method for normal surface enumeration

DOI10.1090/S0025-5718-09-02282-0MaRDI QIDQ3584785zbMATH OpenOpenAlexFDO

Authors 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

double description methodnormal surfacesvertex enumeration

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(8)

• Converting between quadrilateral and standard solution sets in normal surface theory
• Random veering triangulations are not geometric
• Maximal admissible faces and asymptotic bounds for the normal surface solution space
• Computational topology with Regina: algorithms, heuristics and implementations
• Quadrilateral–Octagon Coordinates for Almost Normal Surfaces
• The Weber-Seifert dodecahedral space is non-Haken
• The complexity of the normal surface solution space
• The computational complexity of classical knot recognition

Describes a project that uses

Uses Software

• FXrays
• SnapPea
• Regina

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)