Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Optimizing the double description method for normal surface enumeration

Author: Benjamin A. Burton
Journal: Math. Comp. 79 (2010), 453-484
MSC (2000): Primary 52B55; Secondary 57N10, 57N35
Published electronically: July 14, 2009
MathSciNet review: 2552235
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 52B55, 57N10, 57N35

Retrieve articles in all journals with MSC (2000): 52B55, 57N10, 57N35

Additional Information

Benjamin A. Burton
Affiliation: Department of Mathematics, SMGS, RMIT University, GPO Box 2476V, Melbourne, VIC 3001, Australia
MR Author ID: 739103

Keywords: Normal surfaces; vertex enumeration; double description method
Received by editor(s): August 29, 2008
Published electronically: July 14, 2009
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.