A new approach to crushing 3-manifold triangulations

Burton, Benjamin A. (2013). A new approach to crushing 3-manifold triangulations. In: Proceedings of the Annual Symposium on Computational Geometry. 29th Annual Symposium on Computational Geometry (SoCG 2013), Rio de Janeiro, Brazil, (415-424). 17-20 June 2013. doi:10.1145/2462356.2462409


Author Burton, Benjamin A.
Title of paper A new approach to crushing 3-manifold triangulations
Conference name 29th Annual Symposium on Computational Geometry (SoCG 2013)
Conference location Rio de Janeiro, Brazil
Conference dates 17-20 June 2013
Proceedings title Proceedings of the Annual Symposium on Computational Geometry   Check publisher's open access policy
Journal name Proceedings of the twenty-ninth annual symposium on Computational geometry (SoCG '13)   Check publisher's open access policy
Place of Publication New York, NY United States
Publisher Association for Computing Machinery Inc.
Publication Year 2013
Year available 2013
Sub-type Fully published paper
DOI 10.1145/2462356.2462409
ISBN 9781450320313
1450320317
ISSN 1055-6257
Start page 415
End page 424
Total pages 10
Collection year 2014
Language eng
Formatted Abstract/Summary
The crushing operation of Jaco and Rubinstein is a powerful technique in algorithmic 3-manifold topology: it enabled the
rst practical implementations of 3-sphere recognition and prime decomposition of orientable manifolds, and it plays
a prominent role in state-of-the-art algorithms for unknot recognition and testing for essential surfaces. Although the
crushing operation will always reduce the size of a triangulation, it might alter its topology, and so it requires a careful
theoretical analysis for the settings in which it is used.
The aim of this paper is to make the crushing operation more accessible to practitioners, and easier to generalise to
new settings. When the crushing operation was rst introduced, the analysis was powerful but extremely complex.
Here we give a new treatment that reduces the crushing process to a sequential combination of three\atomic"operations
on a cell decomposition, all of which are simple to analyse.  As an application, we generalise the crushing operation to
the setting of non-orientable 3-manifolds, where we obtain a new practical and robust algorithm for non-orientable prime
decomposition.
Subjects 2605 Computational Mathematics
2608 Geometry and Topology
2614 Theoretical Computer Science
Keyword 0 efficiency
3 manifold triangulations
Computational topology
Normal surfaces
Q-Index Code E1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Conference Paper
Collections: School of Mathematics and Physics
Official 2014 Collection
 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Thu, 28 Nov 2013, 16:57:08 EST by System User on behalf of Examinations