Mathematics – Geometric Topology
Scientific paper
2011-01-16
ISSAC 2011: Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, ACM, 2011, pp. 59-66
Mathematics
Geometric Topology
16 pages, 7 figures, 3 tables; v2: minor revisions; to appear in ISSAC 2011
Scientific paper
10.1145/1993886.1993901
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.
No associations
LandOfFree
Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-284911