Optimizing the double description method for normal surface enumeration

Burton, Benjamin

doi:10.1090/S0025-5718-09-02282-0

Optimizing the double description method for normal surface enumeration
HTML articles powered by AMS MathViewer

by Benjamin A. Burton PDF

Math. Comp. 79 (2010), 453-484 Request permission

Abstract:

Many key algorithms in 3-manifold topology involve the enumeration of normal surfaces, which is based upon the double description method for finding the vertices of a convex polytope. Typically we are only interested in a small subset of these vertices, thus opening the way for substantial optimization. Here we give an account of the vertex enumeration problem as it applies to normal surfaces and present new optimizations that yield strong improvements in both running time and memory consumption. The resulting algorithms are tested using the freely available software package Regina.

References

David Avis, A revised implementation of the reverse search vertex enumeration algorithm, Polytopes—combinatorics and computation (Oberwolfach, 1997) DMV Sem., vol. 29, Birkhäuser, Basel, 2000, pp. 177–198. MR 1785299
David Avis, David Bremner, and Raimund Seidel, How good are convex hull algorithms?, Comput. Geom. 7 (1997), no. 5-6, 265–301. 11th ACM Symposium on Computational Geometry (Vancouver, BC, 1995). MR 1447243, DOI 10.1016/S0925-7721(96)00023-5
David Avis and Komei Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete Comput. Geom. 8 (1992), no. 3, 295–313. ACM Symposium on Computational Geometry (North Conway, NH, 1991). MR 1174359, DOI 10.1007/BF02293050
Benjamin A. Burton, Regina: Normal surface and $3$-manifold topology software, http://regina.sourceforge.net/, 1999–2009.
Benjamin A. Burton, Introducing Regina, the 3-manifold topology software, Experiment. Math. 13 (2004), no. 3, 267–272. MR 2103324
Benjamin A. Burton, Enumeration of non-orientable 3-manifolds using face-pairing graphs and union-find, Discrete Comput. Geom. 38 (2007), no. 3, 527–571. MR 2352707, DOI 10.1007/s00454-007-1307-x
—, Extreme cases in normal surface enumeration, In preparation, 2009.
Patrick J. Callahan, Martin V. Hildebrand, and Jeffrey R. Weeks, A census of cusped hyperbolic $3$-manifolds, Math. Comp. 68 (1999), no. 225, 321–332. With microfiche supplement. MR 1620219, DOI 10.1090/S0025-5718-99-01036-4
Marc Culler and Nathan Dunfield, FXrays: Extremal ray enumeration software, http://www.math.uic.edu/˜t3m/, 2002–2003.
Ulrich Drepper, What every programmer should know about memory, http://people.redhat.com/drepper/cpumemory.pdf, November 2007.
M. E. Dyer, The complexity of vertex enumeration methods, Math. Oper. Res. 8 (1983), no. 3, 381–402. MR 716120, DOI 10.1287/moor.8.3.381
Komei Fukuda and Alain Prodon, Double description method revisited, Combinatorics and computer science (Brest, 1995) Lecture Notes in Comput. Sci., vol. 1120, Springer, Berlin, 1996, pp. 91–111. MR 1448924, DOI 10.1007/3-540-61576-8_{7}7
Wolfgang Haken, Theorie der Normalflächen, Acta Math. 105 (1961), 245–375 (German). MR 141106, DOI 10.1007/BF02559591
Wolfgang Haken, Über das Homöomorphieproblem der 3-Mannigfaltigkeiten. I, Math. Z. 80 (1962), 89–120 (German). MR 160196, DOI 10.1007/BF01162369
Joel Hass, Jeffrey C. Lagarias, and Nicholas Pippenger, The computational complexity of knot and link problems, J. ACM 46 (1999), no. 2, 185–211. MR 1693203, DOI 10.1145/301970.301971
Geoffrey Hemion, The classification of knots and $3$-dimensional spaces, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR 1211184
Craig D. Hodgson and Jeffrey R. Weeks, Symmetries, isometries and length spectra of closed hyperbolic three-manifolds, Experiment. Math. 3 (1994), no. 4, 261–274. MR 1341719
William Jaco, David Letscher, and J. Hyam Rubinstein, Algorithms for essential surfaces in 3-manifolds, Topology and geometry: commemorating SISTAG, Contemp. Math., vol. 314, Amer. Math. Soc., Providence, RI, 2002, pp. 107–124. MR 1941626, DOI 10.1090/conm/314/05426
William Jaco and Ulrich Oertel, An algorithm to decide if a $3$-manifold is a Haken manifold, Topology 23 (1984), no. 2, 195–209. MR 744850, DOI 10.1016/0040-9383(84)90039-9
William Jaco and J. Hyam Rubinstein, $0$-efficient triangulations of 3-manifolds, J. Differential Geom. 65 (2003), no. 1, 61–168. MR 2057531
William Jaco, J. Hyam Rubinstein, and Stephan Tillmann, Coverings and minimal triangulations of $3$-manifolds, Preprint, arXiv:0903.0112, February 2009.
William Jaco and Jeffrey L. Tollefson, Algorithms for the complete decomposition of a closed $3$-manifold, Illinois J. Math. 39 (1995), no. 3, 358–406. MR 1339832
Ensil Kang and J. Hyam Rubinstein, Ideal triangulations of 3-manifolds. I. Spun normal surface theory, Proceedings of the Casson Fest, Geom. Topol. Monogr., vol. 7, Geom. Topol. Publ., Coventry, 2004, pp. 235–265. MR 2172486, DOI 10.2140/gtm.2004.7.235
Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, and Vladimir Gurvich, Generating all vertices of a polyhedron is hard, Discrete Comput. Geom. 39 (2008), no. 1-3, 174–190. MR 2383757, DOI 10.1007/s00454-008-9050-5
Hellmuth Kneser, Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten, Jahresbericht der Deut. Math. Verein. 38 (1929), 248–260.
Sergei V. Matveev, Tables of $3$-manifolds up to complexity $6$, Max-Planck-Institut für Mathematik Preprint Series (1998), no. 67, available from http://www.mpim-bonn.mpg.de/html/preprints/preprints.html.
P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179–184. MR 283691, DOI 10.1112/S0025579300002850
T. S. Motzkin, H. Raiffa, G. L. Thompson, and R. M. Thrall, The double description method, Contributions to the theory of games, vol. 2, Annals of Mathematics Studies, no. 28, Princeton University Press, Princeton, N.J., 1953, pp. 51–73. MR 0060202
Joachim H. Rubinstein, An algorithm to recognize the $3$-sphere, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994) Birkhäuser, Basel, 1995, pp. 601–611. MR 1403961
J. H. Rubinstein, Polyhedral minimal surfaces, Heegaard splittings and decision problems for $3$-dimensional manifolds, Geometric topology (Athens, GA, 1993) AMS/IP Stud. Adv. Math., vol. 2, Amer. Math. Soc., Providence, RI, 1997, pp. 1–20. MR 1470718, DOI 10.1090/amsip/002.1/01
Abigail Thompson, Thin position and the recognition problem for $S^3$, Math. Res. Lett. 1 (1994), no. 5, 613–630. MR 1295555, DOI 10.4310/MRL.1994.v1.n5.a9
Stephan Tillmann, Normal surfaces in topologically finite 3-manifolds, Enseign. Math. (2) 54 (2008), no. 3-4, 329–380. MR 2478091
Jeffrey L. Tollefson, Normal surface $Q$-theory, Pacific J. Math. 183 (1998), no. 2, 359–374. MR 1625962, DOI 10.2140/pjm.1998.183.359
Henry S. Warren, Jr., Hacker’s delight, Addison-Wesley, 2002.