Volume 9, issue 4 (2009)

Download this article
Download this article For screen
For printing
Recent Issues

Volume 15
Issue 4, 1863–2477
Issue 3, 1239–1862
Issue 2, 623–1238
Issue 1, 1–622

Volume 14, 6 issues

Volume 13, 6 issues

Volume 12, 4 issues

Volume 11, 5 issues

Volume 10, 4 issues

Volume 9, 4 issues

Volume 8, 4 issues

Volume 7, 4 issues

Volume 6, 5 issues

Volume 5, 4 issues

Volume 4, 2 issues

Volume 3, 2 issues

Volume 2, 2 issues

Volume 1, 2 issues

The Journal
About the Journal
Editorial Board
Editorial Interests
Editorial Procedure
Submission Guidelines
Submission Page
Author Index
To Appear
ISSN (electronic): 1472-2739
ISSN (print): 1472-2747
Converting between quadrilateral and standard solution sets in normal surface theory

Benjamin A Burton

Algebraic & Geometric Topology 9 (2009) 2121–2174

The enumeration of normal surfaces is a crucial but very slow operation in algorithmic 3–manifold topology. At the heart of this operation is a polytope vertex enumeration in a high-dimensional space (standard coordinates). Tollefson’s Q–theory speeds up this operation by using a much smaller space (quadrilateral coordinates), at the cost of a reduced solution set that might not always be sufficient for our needs. In this paper we present algorithms for converting between solution sets in quadrilateral and standard coordinates. As a consequence we obtain a new algorithm for enumerating all standard vertex normal surfaces, yielding both the speed of quadrilateral coordinates and the wider applicability of standard coordinates. Experimentation with the software package Regina shows this new algorithm to be extremely fast in practice, improving speed for large cases by factors from thousands up to millions.

normal surfaces, Q-theory, vertex enumeration, conversion algorithm, double description method
Mathematical Subject Classification 2000
Primary: 52B55
Secondary: 57N10, 57N35
Received: 23 February 2009
Accepted: 1 September 2009
Published: 21 October 2009
Benjamin A Burton
School of Mathematics and Physics
The University of Queensland Brisbane QLD 4072