Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

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
Email: bab@debian.org

DOI: http://dx.doi.org/10.1090/S0025-5718-09-02282-0
PII: S 0025-5718(09)02282-0
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.