Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations

Burton, Benjamin A. (2011). Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations. In: ISSAC 2011: Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation. 36th International Symposium on Symbolic and Algebraic Computation [ISSAC], San Jose, CA, United States, (59-66). 8-11 June 2011. doi:10.1145/1993886.1993901

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 of paper Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations
Conference name 36th International Symposium on Symbolic and Algebraic Computation [ISSAC]
Conference location San Jose, CA, United States
Conference dates 8-11 June 2011
Proceedings title ISSAC 2011: Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation
Journal name Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
Place of Publication New York, NY, United States
Publisher ACM Press
Publication Year 2011
Sub-type Fully published paper
DOI 10.1145/1993886.1993901
ISBN 9781450306751
Start page 59
End page 66
Total pages 8
Language eng
Abstract/Summary Enumerating all 3-manifold triangulations of a given size is a difficult but increasingly important problem in computational topology. A key difficulty for enumeration algorithms is that most combinatorial triangulations must be discarded because they do not represent topological 3-manifolds. In this paper we show how to preempt bad triangulations by detecting genus in partially-constructed vertex links, allowing us to prune the enumeration tree substantially. The key idea is to manipulate the boundary edges surrounding partial vertex links using expected logarithmic time operations. Practical testing shows the resulting enumeration algorithm to be significantly faster, with up to 249x speed-ups even for small problems where comparisons are feasible. We also discuss parallelisation, and describe new data sets that have been obtained using high-performance computing facilities.
Q-Index Code E1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Conference Paper
Collections: School of Mathematics and Physics
Official 2012 Collection
 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 9 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Wed, 29 Jun 2011, 17:29:35 EST by Dr Benjamin Burton on behalf of School of Mathematics & Physics