Converting between quadrilateral and standard solution sets in normal surface theory

Burton, Benjamin A¹

¹School of Mathematics and Physics, The University of Queensland Brisbane QLD 4072, Australia

Algebraic and Geometric Topology, Tome 9 (2009) no. 4, pp. 2121-2174

Résumé

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.

Détail

DOI : 10.2140/agt.2009.9.2121

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

Bibliographie

[1] D Avis, D Bremner, R Seidel, How good are convex hull algorithms?, Comput. Geom. 7 (1997) 265

[2] A Brøndsted, An introduction to convex polytopes, 90, Springer (1983)

[3] B A Burton, Regina : Normal surface and 3–manifold topology software (1999–2009)

[4] B A Burton, Introducing Regina, the 3–manifold topology software, Experiment. Math. 13 (2004) 267

[5] B A Burton, Extreme cases in normal surface enumeration, in preparation (2009)

[6] B A Burton, Optimizing the double description method for normal surface enumeration, Math. Comp. 79 (2010) 453

[7] M Culler, N Dunfield, FXrays: Extremal ray enumeration software (2002–2003)

[8] W Eberly, M Giesbrecht, P Giorgi, A Storjohann, G Villard, Solving sparse rational linear systems, from: "ISSAC 2006", ACM (2006) 63

[9] K Fukuda, A Prodon, Double description method revisited, from: "Combinatorics and computer science (Brest, 1995)", Lecture Notes in Comput. Sci. 1120, Springer (1996) 91

[10] W Haken, Theorie der Normalflächen, Acta Math. 105 (1961) 245

[11] W Haken, Über das Homöomorphieproblem der 3–Mannigfaltigkeiten I, Math. Z. 80 (1962) 89

[12] J Hass, J C Lagarias, N Pippenger, The computational complexity of knot and link problems, J. ACM 46 (1999) 185

[13] C D Hodgson, J R Weeks, Symmetries, isometries and length spectra of closed hyperbolic three-manifolds, Experiment. Math. 3 (1994) 261

[14] W Jaco, U Oertel, An algorithm to decide if a 3–manifold is a Haken manifold, Topology 23 (1984) 195

[15] W Jaco, J H Rubinstein, 0–efficient triangulations of 3–manifolds, J. Differential Geom. 65 (2003) 61

[16] W Jaco, J L Tollefson, Algorithms for the complete decomposition of a closed 3–manifold, Illinois J. Math. 39 (1995) 358

[17] H Kneser, Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten, Jahresbericht der Deut. Math. Verein. 38 (1929) 248

[18] S Matsumoto, R Rannard, The regular projective solution space of the figure-eight knot complement, Experiment. Math. 9 (2000) 221

[19] T S Motzkin, H Raiffa, G L Thompson, R M Thrall, The double description method, from: "Contributions to the theory of games, vol. 2", Annals of Mathematics Studies 28, Princeton University Press (1953) 51

[20] J H Rubinstein, An algorithm to recognize the 3–sphere, from: "Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994)", Birkhäuser (1995) 601

[21] J H Rubinstein, Polyhedral minimal surfaces, Heegaard splittings and decision problems for 3–dimensional manifolds, from: "Geometric topology (Athens, GA, 1993)", AMS/IP Stud. Adv. Math. 2, Amer. Math. Soc. (1997) 1

[22] A Thompson, Thin position and the recognition problem for S3, Math. Res. Lett. 1 (1994) 613

[23] W P Thurston, The geometry and topology of 3–manifolds, lecture notes, Princeton University (1978)

[24] S Tillmann, Normal surfaces in topologically finite 3–manifolds, Enseign. Math. (2) 54 (2008) 329

[25] J L Tollefson, Normal surface Q–theory, Pacific J. Math. 183 (1998) 359