Mathematics – Geometric Topology
Scientific paper
2010-11-18
SCG '11: Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, ACM, 2011, pp. 153-162
Mathematics
Geometric Topology
17 pages, 4 figures, 4 tables; v2: incorporate connectedness into Theorem 4, other minor revisions; to appear in SoCG 2011
Scientific paper
10.1145/1998196.1998220
It is important to have fast and effective methods for simplifying 3-manifold triangulations without losing any topological information. In theory this is difficult: we might need to make a triangulation super-exponentially more complex before we can make it smaller than its original size. Here we present experimental work suggesting that for 3-sphere triangulations the reality is far different: we never need to add more than two tetrahedra, and we never need more than a handful of local modifications. If true in general, these extremely surprising results would have significant implications for decision algorithms and the study of triangulations in 3-manifold topology. The algorithms behind these experiments are interesting in their own right. Key techniques include the isomorph-free generation of all 3-manifold triangulations of a given size, polynomial-time computable signatures that identify triangulations uniquely up to isomorphism, and parallel algorithms for studying finite level sets in the infinite Pachner graph.
No associations
LandOfFree
The Pachner graph and the simplification of 3-sphere 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 The Pachner graph and the simplification of 3-sphere triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Pachner graph and the simplification of 3-sphere triangulations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-536727