Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Optimizing the double description method for normal surface enumeration


Author: Benjamin A. Burton
Journal: Math. Comp. 79 (2010), 453-484
MSC (2000): Primary 52B55; Secondary 57N10, 57N35
DOI: https://doi.org/10.1090/S0025-5718-09-02282-0
Published electronically: July 14, 2009
MathSciNet review: 2552235
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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 (2001f:52030)
  • 2. David Avis, David Bremner, and Raimund Seidel, How good are convex hull algorithms?, Comput. Geom. 7 (1997), no. 5-6, 265-301. MR 1447243 (98c:52017)
  • 3. 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. MR 1174359 (93h:68137)
  • 4. Benjamin A. Burton, Regina: Normal surface and $ 3$-manifold topology software, http:// regina.sourceforge.net/, 1999-2009.
  • 5. -, Introducing Regina, the $ 3$-manifold topology software, Experiment. Math. 13 (2004), no. 3, 267-272. MR 2103324 (2005g:57042)
  • 6. -, Enumeration of non-orientable $ 3$-manifolds using face-pairing graphs and union-find, Discrete Comput. Geom. 38 (2007), no. 3, 527-571. MR 2352707
  • 7. -, Extreme cases in normal surface enumeration, In preparation, 2009.
  • 8. 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. MR 1620219 (99c:57035)
  • 9. Marc Culler and Nathan Dunfield, FXrays: Extremal ray enumeration software, http:// www.math.uic.edu/˜t3m/, 2002-2003.
  • 10. Ulrich Drepper, What every programmer should know about memory, http://people.redhat.com/drepper/cpumemory.pdf, November 2007.
  • 11. M. E. Dyer, The complexity of vertex enumeration methods, Math. Oper. Res. 8 (1983), no. 3, 381-402. MR 716120 (85j:68102)
  • 12. 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 (98c:90108)
  • 13. Wolfgang Haken, Theorie der Normalflächen, Acta Math. 105 (1961), 245-375. MR 0141106 (25:4519a)
  • 14. -, Über das Homöomorphieproblem der $ 3$-Mannigfaltigkeiten. I, Math. Z. 80 (1962), 89-120. MR 0160196 (28:3410)
  • 15. Joel Hass, Jeffrey C. Lagarias, and Nicholas Pippenger, The computational complexity of knot and link problems, J. Assoc. Comput. Mach. 46 (1999), no. 2, 185-211. MR 1693203 (2000g:68056)
  • 16. Geoffrey Hemion, The classification of knots and $ 3$-dimensional spaces, Oxford Science Publications, Oxford University Press, Oxford, 1992. MR 1211184 (94g:57015)
  • 17. 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 (97a:57013)
  • 18. William Jaco, David Letscher, and J. Hyam Rubinstein, Algorithms for essential surfaces in $ 3$-manifolds, Topology and Geometry: Commemorating SISTAG, Contemporary Mathematics, no. 314, Amer. Math. Soc., Providence, RI, 2002, pp. 107-124. MR 1941626 (2003m:57043)
  • 19. 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 (85j:57014)
  • 20. William Jaco and J. Hyam Rubinstein, 0-efficient triangulations of $ 3$-manifolds, J. Differential Geom. 65 (2003), no. 1, 61-168. MR 2057531 (2005d:57034)
  • 21. William Jaco, J. Hyam Rubinstein, and Stephan Tillmann, Coverings and minimal triangulations of $ 3$-manifolds, Preprint, arXiv:0903.0112, February 2009.
  • 22. 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 (97a:57014)
  • 23. 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 (2006g:57035)
  • 24. 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 (2008m:05281)
  • 25. Hellmuth Kneser, Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten, Jahresbericht der Deut. Math. Verein. 38 (1929), 248-260.
  • 26. 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.
  • 27. P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179-184. MR 0283691 (44:921)
  • 28. T. S. Motzkin, H. Raiffa, G. L. Thompson, and R. M. Thrall, The double description method, Contributions to the Theory of Games, Vol. II (H. W. Kuhn and A. W. Tucker, eds.), Annals of Mathematics Studies, no. 28, Princeton University Press, Princeton, NJ, 1953, pp. 51-73. MR 0060202 (15:638g)
  • 29. J. Hyam Rubinstein, An algorithm to recognize the $ 3$-sphere, Proceedings of the International Congress of Mathematicians (Zürich, 1994), vol. 1, Birkhäuser, 1995, pp. 601-611. MR 1403961 (97e:57011)
  • 30. -, 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., 1997, pp. 1-20. MR 1470718 (98f:57030)
  • 31. Abigail Thompson, Thin position and the recognition problem for $ S\sp 3$, Math. Res. Lett. 1 (1994), no. 5, 613-630. MR 1295555 (95k:57015)
  • 32. Stephan Tillmann, Normal surfaces in topologically finite $ 3$-manifolds, Enseign. Math. (2) 54 (2008), 329-380. MR 2478091
  • 33. Jeffrey L. Tollefson, Normal surface $ Q$-theory, Pacific J. Math. 183 (1998), no. 2, 359-374. MR 1625962 (99c:57047)
  • 34. Henry S. Warren, Jr., Hacker's delight, Addison-Wesley, 2002.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 52B55, 57N10, 57N35

Retrieve articles in all journals with MSC (2000): 52B55, 57N10, 57N35


Additional Information

Benjamin A. Burton
Affiliation: Department of Mathematics, SMGS, RMIT University, GPO Box 2476V, Melbourne, VIC 3001, Australia
Email: bab@debian.org

DOI: https://doi.org/10.1090/S0025-5718-09-02282-0
Keywords: Normal surfaces; vertex enumeration; double description method
Received by editor(s): August 29, 2008
Published electronically: July 14, 2009
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society