Document Open Access Logo

Efficient Algorithms to Decide Tightness

Authors Bhaskar Bagchi, Basudeb Datta, Benjamin A. Burton, Nitin Singh, Jonathan Spreer

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2016.12.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • discrete geometry and topology
  • polynomial time algorithms
  • fixed parameter tractability
  • tight triangulations
  • simplicial complexes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Tightness is a generalisation of the notion of convexity: a space is tight if and only if it is "as convex as possible", given its topological constraints. For a simplicial complex, deciding tightness has a straightforward exponential time algorithm, but more efficient methods to decide tightness are only known in the trivial setting of triangulated surfaces.

In this article, we present a new polynomial time procedure to decide tightness for triangulations of 3-manifolds - a problem which previously was thought to be hard. In addition, for the more difficult problem of deciding tightness of 4-dimensional combinatorial manifolds, we describe an algorithm that is fixed parameter tractable in the treewidth of the 1-skeletons of the vertex links. Finally, we show that simpler treewidth parameters are not viable: for all non-trivial inputs, we show that the treewidths of both the 1-skeleton and the dual graph must grow too quickly for a standard treewidth-based algorithm to remain tractable.

Cite As Get BibTex

Bhaskar Bagchi, Basudeb Datta, Benjamin A. Burton, Nitin Singh, and Jonathan Spreer. Efficient Algorithms to Decide Tightness. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.12

Author Details

Bhaskar Bagchi
Basudeb Datta
Benjamin A. Burton
Nitin Singh
Jonathan Spreer

References

  1. Aleksandr D. Alexandrov. On a class of closed surfaces. Recueil Math. (Moscow), 4:69-72, 1938. Google Scholar
  2. Bhaskar Bagchi. The mu vector, Morse inequalities and a generalized lower bound theorem for locally tame combinatorial manifolds. European J. Combin., 51:69-83, 2016. Google Scholar
  3. Bhaskar Bagchi and Basudeb Datta. On stellated spheres and a tightness criterion for combinatorial manifolds. European J. Combin., 36:294-313, 2014. Google Scholar
  4. Bhaskar Bagchi, Basudeb Datta, and Jonathan Spreer. Tight triangulations of closed 3-manifolds. European J. Combin., 54:103-120, 2016. Google Scholar
  5. Thomas F. Banchoff. Critical points and curvature for embedded polyhedral surfaces. Amer. Math. Monthly, 77:475-485, 1970. Google Scholar
  6. Ulrich Brehm and Wolfgang Kühnel. 15-vertex triangulations of an 8-manifold. Math. Ann., 294(1):167-193, 1992. Google Scholar
  7. Benjamin A. Burton. A new approach to crushing 3-manifold triangulations. Discrete Comput. Geom., 52(1):116-139, 2014. Google Scholar
  8. Benjamin A. Burton, Basudeb Datta, Nitin Singh, and Jonathan Spreer. A construction principle for tight and minimal triangulations of manifolds, 2015. 27 pages, 2 figures. URL: http://arxiv.org/abs/1511.04500.
  9. Benjamin A. Burton and Rodney G. Downey. Courcelle’s theorem for triangulations. arXiv:1403.2926 [math.GT], 24 pages , 7 figures, 2014. Google Scholar
  10. Benjamin A. Burton, Thomas Lewiner, João Paixão, and Jonathan Spreer. Parameterized complexity of discrete morse theory. In Proceedings of the Twenty-Ninth Annual Symposium on Computational Geometry, pages 127-136. ACM SIAM, 2013. Google Scholar
  11. Benjamin A. Burton, Clément Maria, and Jonathan Spreer. Algorithms and complexity for Turaev-Viro invariants. In Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part 1, pages 281-293. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_23.
  12. Benjamin A. Burton and Jonathan Spreer. The complexity of detecting taut angle structures on triangulations. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 168-183. ACM SIAM, 2013. URL: http://arxiv.org/abs/1207.0904.
  13. Benjamin A. Burton and Jonathan Spreer. Computationally proving triangulated 4-manifolds to be diffeomorphic, 2013. 29th ACM Symposium on Computational Geometry, Young Researchers Forum, Collections of abstracts, 2013, pages 15-16. Google Scholar
  14. Mario Casella and Wolfgang Kühnel. A triangulated K3 surface with the minimum number of vertices. Topology, 40(4):753-772, 2001. Google Scholar
  15. Shiing-Shen Chern and Richard K. Lashof. On the total curvature of immersed manifolds. Amer. J. Math., 79:306-318, 1957. Google Scholar
  16. Ákos Császár. A polyhedron without diagonals. Acta Univ. Szeged. Sect. Sci. Math., 13:140-142, 1949. Google Scholar
  17. Basudeb Datta and Nitin Singh. An infinite family of tight triangulations of manifolds. J. Combin. Theory Ser. A, 120(8):2148-2163, 2013. Google Scholar
  18. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity, volume 3. Springer, 1999. Google Scholar
  19. Herbert Edelsbrunner and John L. Harer. Computational Topology: An Introduction. Applied Mathematics. American Mathematical Society, 2010. Google Scholar
  20. Felix Effenberger. Stacked polytopes and tight triangulations of manifolds. J. Combin. Theory Ser. A, 118(6):1843-1862, 2011. Google Scholar
  21. Robin Forman. Morse theory for cell complexes. Adv. Math., 134(1):90-145, 1998. Google Scholar
  22. Joel Hass and Greg Kuperberg. The complexity of recognizing the 3-sphere. Oberwolfach Reports, 24:1425-1426, 2012. Google Scholar
  23. Joel Hass, Jeffrey C. Lagarias, and Nicholas Pippenger. The computational complexity of knot and link problems. J. ACM, 46(2):185-211, 1999. Google Scholar
  24. Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002. Google Scholar
  25. Michael Joswig and Marc E. Pfetsch. Computing optimal Morse matchings. SIAM J. Discrete Math., 20(1):11-25, 2006. Google Scholar
  26. Ton Kloks. Treewidth: Computations and Approximations, volume 842. Springer, 1994. Google Scholar
  27. Wolfgang Kühnel. Tight polyhedral submanifolds and tight triangulations, volume 1612 of Lecture Notes in Math. Springer-Verlag, Berlin, 1995. Google Scholar
  28. Wolfgang Kühnel and Thomas F. Banchoff. The 9-vertex complex projective plane. Math. Intelligencer, 5(3):11-22, 1983. Google Scholar
  29. Wolfgang Kühnel and Frank H. Lutz. A census of tight triangulations. Period. Math. Hungar., 39(1-3):161-183, 1999. Discrete geometry and rigidity (Budapest, 1999). Google Scholar
  30. Nicolaas H. Kuiper. Immersions with minimal total absolute curvature. In Colloque Géom. Diff. Globale (Bruxelles, 1958), pages 75-88. Centre Belge Rech. Math., Louvain, 1959. Google Scholar
  31. Nicolaas H. Kuiper. Morse relations for curvature and tightness. In Proceedings of Liverpool Singularities Symposium, II, volume 209 of Lecture Notes in Math., pages 77-89, 1971. Google Scholar
  32. Greg Kuperberg. Knottedness is in np, modulo GRH. Adv. Math., 256:493-506, 2014. Google Scholar
  33. Thomas Lewiner, Lopes Hélio, and Geovan Tavares. Toward optimality in discrete Morse theory. Experiment. Math., 12(3):271-285, 2003. Google Scholar
  34. John Milnor. On the relationship between the Betti numbers of a hypersurface and an integral of its Gaussian curvature (1950). In Collected papers. Vol. 1, Geometry, pages 15-26. Publish or Perish Inc., Houston, TX, 1994. Google Scholar
  35. Saul Schleimer. Sphere recognition lies in NP. In Low-dimensional and symplectic topology, volume 82 of Proc. Sympos. Pure Math., pages 183-213. Amer. Math. Soc., 2011. Google Scholar
  36. Martin Tancer. Recognition of collapsible complexes is np-complete. arXiv:1211.6254 [cs.CG], 21 pages, 13 figures, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact