Optimizing the double description method for normal surface enumeration

Burton, Benjamin A. (2010) Optimizing the double description method for normal surface enumeration. Mathematics of Computation, 79 269: 453-484. doi:10.1090/S0025-5718-09-02282-0

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Burton, Benjamin A.
Title Optimizing the double description method for normal surface enumeration
Journal name Mathematics of Computation   Check publisher's open access policy
ISSN 0025-5718
1088-6842
Publication date 2010-01
Year available 2009
Sub-type Article (original research)
DOI 10.1090/S0025-5718-09-02282-0
Volume 79
Issue 269
Start page 453
End page 484
Total pages 32
Editor Chi-Wang Shu
Place of publication Providence, RI, U.S.A.
Publisher American Mathematical Society
Collection year 2010
Language eng
Subject C1
970101 Expanding Knowledge in the Mathematical Sciences
010112 Topology
Formatted 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.
Keyword Normal surfaces
Vertex enumeration
Double description method
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Non-UQ
Additional Notes Published online July 14, 2009.

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
ERA 2012 Admin Only
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 10 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 12 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Wed, 21 Apr 2010, 16:18:57 EST by Kay Mackie on behalf of School of Mathematics & Physics