More Web Proxy on the site http://driver.im/

research-article

The complexity of the normal surface solution space

Author:

Benjamin A. BurtonAuthors Info & Claims

SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometry

Pages 201 - 209

https://doi.org/10.1145/1810959.1810995

Published: 13 June 2010 Publication History

Abstract

Normal surface theory is a central tool in algorithmic three-dimensional topology, and the enumeration of vertex normal surfaces is the computational bottleneck in many important algorithms. However, it is not well understood how the number of such surfaces grows in relation to the size of the underlying triangulation. Here we address this problem in both theory and practice. In theory, we tighten the exponential upper bound substantially; furthermore, we construct pathological triangulations that prove an exponential bound to be unavoidable. In practice, we undertake a comprehensive analysis of millions of triangulations and find that in general the number of vertex normal surfaces is remarkably small, with strong evidence that our pathological triangulations may in fact be the worst case scenarios. This analysis is the first of its kind, and the striking behaviour that we observe has important implications for the feasibility of topological algorithms in three dimensions.

References

[1]

I. Agol, J. Hass, and W. Thurston. 3-manifold knot genus is NP-complete. In STOC '02: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, pages 761--766. ACM Press, 2002.

Digital Library

[2]

D. Avis, D. Bremner, and R. Seidel. How good are convex hull algorithms? Comput. Geom., 7(5-6):265--301, 1997.

Digital Library

[3]

B. A. Burton. Regina: Normal surface and 3-manifold topology software. http://regina.sourceforge.net/, 1999--2009.

[4]

B. A. Burton. Introducing Regina, the 3-manifold topology software. Experiment. Math., 13(3):267--272, 2004.

[5]

B. A. Burton. Enumeration of non-orientable 3-manifolds using face-pairing graphs and union-find. Discrete Comput. Geom., 38(3):527--571, 2007.

Digital Library

[6]

B. A. Burton. Structures of small closed non-orientable 3-manifold triangulations. J. Knot Theory Ramifications, 16(5):545--574, 2007.

[7]

B. A. Burton. Converting between quadrilateral and standard solution sets in normal surface theory. Algebr. Geom. Topol., 9(4):2121--2174, 2009.

[8]

B. A. Burton. Quadrilateral-octagon coordinates for almost normal surfaces. To appear in Experiment. Math., arXiv:0904.3041, Apr. 2009.

[9]

B. A. Burton. Optimizing the double description method for normal surface enumeration. Math. Comp., 79(269):453--484, 2010.

[10]

B. A. Burton, J. H. Rubinstein, and S. Tillmann. The Weber-Seifert dodecahedral space is non-Haken. Preprint, arXiv:0909.4625, Sept. 2009.

[11]

P. J. Callahan, M. V. Hildebrand, and J. R. Weeks. A census of cusped hyperbolic 3-manifolds. Math. Comp., 68(225):321--332, 1999.

Digital Library

[12]

M. E. Dyer. The complexity of vertex enumeration methods. Math. Oper. Res., 8(3):381--402, 1983.

Digital Library

[13]

B. Grünbaum. Convex Polytopes. Number 221 in Graduate Texts in Mathematics. Springer, New York, 2nd edition, 2003.

[14]

W. Haken. Theorie der Normalflächen. Acta Math., 105:245--375, 1961.

[15]

W. Haken. Über das Homöomorphieproblem der 3-Mannigfaltigkeiten. I. Math. Z., 80:89--120, 1962.

[16]

J. Hass, J. C. Lagarias, and N. Pippenger. The computational complexity of knot and link problems. J. Assoc. Comput. Mach., 46(2):185--211, 1999.

Digital Library

[17]

W. Jaco and U. Oertel. An algorithm to decide if a 3-manifold is a Haken manifold. Topology, 23(2):195--209, 1984.

[18]

W. Jaco, H. Rubinstein, and S. Tillmann. Minimal triangulations for an infinite family of lens spaces. J. Topol., 2(1):157--180, 2009.

[19]

W. Jaco and J. H. Rubinstein. 0-efficient triangulations of 3-manifolds. J. Differential Geom., 65(1):61--168, 2003.

[20]

W. Jaco, J. H. Rubinstein, and S. Tillmann. Coverings and minimal triangulations of 3-manifolds. To appear in Algebr. Geom. Topol., arXiv:0903.0112, Feb. 2009.

[21]

W. Jaco and J. L. Tollefson. Algorithms for the complete decomposition of a closed 3-manifold. Illinois J. Math., 39(3):358--406, 1995.

[22]

L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, and V. Gurvich. Generating all vertices of a polyhedron is hard. Discrete Comput. Geom., 39(1-3):174--190, 2008.

Digital Library

[23]

H. Kneser. Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten. Jahresbericht der Deut. Math. Verein., 38:248--260, 1929.

[24]

T. Li. An algorithm to determine the Heegaard genus of a 3-manifold. Preprint, arXiv:1002.1958, Feb. 2010.

[25]

A. A. Markov. Insolubility of the problem of homeomorphy. In Proc. Internat. Congress Math. 1958, pages 300--306. Cambridge Univ. Press, New York, 1960.

[26]

B. Martelli and C. Petronio. Three-manifolds having complexity at most 9. Experiment. Math., 10(2):207--236, 2001.

[27]

W. S. Massey. A Basic Course in Algebraic Topology. Number 127 in Graduate Texts in Mathematics. Springer-Verlag, New York, 1991.

[28]

S. Matsumoto and R. Rannard. The regular projective solution space of the figure-eight knot complement. Experiment. Math., 9(2):221--234, 2000.

[29]

S. V. Matveev. Tables of 3-manifolds up to complexity 6. Max-Planck-Institut für Mathematik Preprint Series, (67), 1998. Available from http://www.mpim-bonn.mpg.de/html/preprints/preprints.html.

[30]

S. V. Matveev. Recognition and tabulation of three-dimensional manifolds. Dokl. Akad. Nauk, 400(1):26--28, 2005.

[31]

P. McMullen. The maximum numbers of faces of a convex polytope. Mathematika, 17:179--184, 1970.

[32]

J. H. Rubinstein. An algorithm to recognize the 3-sphere. In Proceedings of the International Congress of Mathematicians (Zürich, 1994), volume 1, pages 601--611. Birkhäuser, 1995.

[33]

J. H. Rubinstein. Polyhedral minimal surfaces, Heegaard splittings and decision problems for 3-dimensional manifolds. In Geometric Topology (Athens, GA, 1993), volume 2 of AMS/IP Stud. Adv. Math., pages 1--20. Amer. Math. Soc., 1997.

[34]

A. Thompson. Thin position and the recognition problem for S^3. Math. Res. Lett., 1(5):613--630, 1994.

[35]

W. P. Thurston. The geometry and topology of 3-manifolds. Lecture notes, Princeton University, 1978.

[36]

W. P. Thurston. Three-dimensional manifolds, Kleinian groups and hyperbolic geometry. Bull. Amer. Math. Soc. (N.S.), 6(3):357--381, 1982.

[37]

J. L. Tollefson. Normal surface Q-theory. Pacific J. Math., 183(2):359--374, 1998.

Cited By

Ichihara KNishimura YTani S(2023)The computational complexity of classical knot recognitionJournal of Knot Theory and Its Ramifications10.1142/S021821652350069432:11Online publication date: 10-Oct-2023
https://doi.org/10.1142/S0218216523500694
Erickson JNayyeri A(2013)Tracing Compressed Curves in Triangulated SurfacesDiscrete & Computational Geometry10.1007/s00454-013-9515-z49:4(823-863)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s00454-013-9515-z
Burton BOzlen M(2013)A Tree Traversal Algorithm for Decision Problems in Knot Theory and 3-Manifold TopologyAlgorithmica10.1007/s00453-012-9645-365:4(772-801)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1007/s00453-012-9645-3
Show More Cited By

Index Terms

The complexity of the normal surface solution space
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations
ISSAC '11: Proceedings of the 36th international symposium on Symbolic and algebraic computation

Enumerating all 3-manifold triangulations of a given size is a difficult but increasingly important problem in computational topology. A key difficulty for enumeration algorithms is that most combinatorial triangulations must be discarded because they ...
Maximal admissible faces and asymptotic bounds for the normal surface solution space

The enumeration of normal surfaces is a key bottleneck in computational three-dimensional topology. The underlying procedure is the enumeration of admissible vertices of a high-dimensional polytope, where admissibility is a powerful but non-linear and ...
Quading triangular meshes with certain topological constraints

In computer graphics and geometric modeling, shapes are often represented by triangular meshes (also called 3D meshes or manifold triangulations). The quadrangulation of a triangular mesh has wide applications. In this paper, we present a novel method ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometry

June 2010

452 pages

ISBN:9781450300162

DOI:10.1145/1810959

Program Chairs:
David Kirkpatrick
University of British Columbia, Canada
,
Joseph Mitchell
SUNY Stony Brook, USA

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '10

Sponsor:

SoCG '10: Symposium on Computational Geometry

June 13 - 16, 2010

Utah, Snowbird, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
132
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ichihara KNishimura YTani S(2023)The computational complexity of classical knot recognitionJournal of Knot Theory and Its Ramifications10.1142/S021821652350069432:11Online publication date: 10-Oct-2023
https://doi.org/10.1142/S0218216523500694
Erickson JNayyeri A(2013)Tracing Compressed Curves in Triangulated SurfacesDiscrete & Computational Geometry10.1007/s00454-013-9515-z49:4(823-863)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s00454-013-9515-z
Burton BOzlen M(2013)A Tree Traversal Algorithm for Decision Problems in Knot Theory and 3-Manifold TopologyAlgorithmica10.1007/s00453-012-9645-365:4(772-801)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1007/s00453-012-9645-3
Erickson JNayyeri ADey TWhitesides S(2012)Tracing compressed curves in triangulated surfacesProceedings of the twenty-eighth annual symposium on Computational geometry10.1145/2261250.2261270(131-140)Online publication date: 17-Jun-2012
https://dl.acm.org/doi/10.1145/2261250.2261270
Burton BHurtado Fvan Kreveld M(2011)The pachner graph and the simplification of 3-sphere triangulationsProceedings of the twenty-seventh annual symposium on Computational geometry10.1145/1998196.1998220(153-162)Online publication date: 13-Jun-2011
https://dl.acm.org/doi/10.1145/1998196.1998220
Burton BOzlen MHurtado Fvan Kreveld M(2011)A tree traversal algorithm for decision problems in knot theory and 3-manifold topologyProceedings of the twenty-seventh annual symposium on Computational geometry10.1145/1998196.1998219(145-152)Online publication date: 13-Jun-2011
https://dl.acm.org/doi/10.1145/1998196.1998219
Dunfield NHirani AHurtado Fvan Kreveld M(2011)The least spanning area of a knot and the optimal bounding chain problemProceedings of the twenty-seventh annual symposium on Computational geometry10.1145/1998196.1998218(135-144)Online publication date: 13-Jun-2011
https://dl.acm.org/doi/10.1145/1998196.1998218
Burton BSchost ÉEmiris I(2011)Detecting genus in vertex links for the fast enumeration of 3-manifold triangulationsProceedings of the 36th international symposium on Symbolic and algebraic computation10.1145/1993886.1993901(59-66)Online publication date: 8-Jun-2011
https://dl.acm.org/doi/10.1145/1993886.1993901

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten