Converting between quadrilateral and standard solution sets in normal surface theory

Burton, Benjamin A

doi:10.2140/agt.2009.9.2121

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the Journal

Editorial Board

Subscriptions

Submission Guidelines

Submission Page

Policies for Authors

Ethics Statement

ISSN 1472-2739 (online)

ISSN 1472-2747 (print)

Author Index

To Appear

Other MSP Journals

Converting between quadrilateral and standard solution sets in normal surface theory

Benjamin A Burton

Algebraic & Geometric Topology 9 (2009) 2121–2174

DOI: 10.2140/agt.2009.9.2121

Abstract

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.

Keywords

normal surfaces, Q-theory, vertex enumeration, conversion algorithm, double description method

Mathematical Subject Classification 2000

Primary: 52B55

Secondary: 57N10, 57N35

References

Publication

Received: 23 February 2009

Accepted: 1 September 2009

Published: 21 October 2009

Authors

Benjamin A Burton
School of Mathematics and Physics The University of Queensland Brisbane QLD 4072 Australia

Volume 9, issue 4 (2009)