Document Open Access Logo

Counting Polygon Triangulations is Hard

Author David Eppstein

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.33.pdf
  • Filesize: 0.88 MB
  • 17 pages

Document Identifiers

Author Details

David Eppstein
  • Computer Science Department, University of California, Irvine, USA

Funding

  • Eppstein, David: Supported in part by NSF grants CCF-1618301 and CCF-1616248.

Cite AsGet BibTex

David Eppstein. Counting Polygon Triangulations is Hard. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.33

Abstract

We prove that it is #P-complete to count the triangulations of a (non-simple) polygon.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Problems, reductions and completeness
Keywords
  • counting complexity
  • #P-completeness
  • triangulation
  • polygons

Metrics

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

References

  1. Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann, and Birgit Vogtenhuber. An improved lower bound on the minimum number of triangulations. In Sándor Fekete and Anna Lubiw, editors, Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages A7:1-A7:16, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.7.
  2. Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser, and Birgit Vogtenhuber. On the number of plane geometric graphs. Graphs and Combinatorics, 23(suppl. 1):67-84, 2007. URL: http://dx.doi.org/10.1007/s00373-007-0704-5.
  3. Oswin Aichholzer, Ferran Hurtado, and Marc Noy. A lower bound on the number of triangulations of planar point sets. Comput. Geom. Theory and Applications, 29(2):135-145, 2004. URL: http://dx.doi.org/10.1016/j.comgeo.2004.02.003.
  4. Oswin Aichholzer, David Orden, Francisco Santos, and Bettina Speckmann. On the number of pseudo-triangulations of certain point sets. J. Combin. Theory Ser. A, 115(2):254-278, 2008. URL: http://dx.doi.org/10.1016/j.jcta.2007.06.002.
  5. Victor Alvarez, Karl Bringmann, Radu Curticapean, and Saurabh Ray. Counting triangulations and other crossing-free structures via onion layers. Discrete Comput. Geom., 53(4):675-690, 2015. URL: http://dx.doi.org/10.1007/s00454-015-9672-3.
  6. Victor Alvarez, Karl Bringmann, Saurabh Ray, and Raimund Seidel. Counting triangulations and other crossing-free structures approximately. Comput. Geom. Theory and Applications, 48(5):386-397, 2015. URL: http://dx.doi.org/10.1016/j.comgeo.2014.12.006.
  7. Victor Alvarez and Raimund Seidel. A simple aggregative algorithm for counting triangulations of planar point sets and related problems. In Timothy Chan and Rolf Klein, editors, Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG'13), pages 1-8, New York, 2013. ACM. URL: http://dx.doi.org/10.1145/2462356.2462392.
  8. Emile E. Anclin. An upper bound for the number of planar lattice triangulations. J. Combin. Theory Ser. A, 103(2):383-386, 2003. URL: http://dx.doi.org/10.1016/S0097-3165(03)00097-9.
  9. Takao Asano, Tetsuo Asano, and Hiroshi Imai. Partitioning a polygonal region into trapezoids. J. ACM, 33(2):290-312, 1986. URL: http://dx.doi.org/10.1145/5383.5387.
  10. Andrei Asinowski and Günter Rote. Point sets with many non-crossing perfect matchings. Comput. Geom. Theory and Applications, 68:7-33, 2018. URL: http://dx.doi.org/10.1016/j.comgeo.2017.05.006.
  11. Marshall W. Bern and David Eppstein. Mesh generation and optimal triangulation. In Ding-Zhu Du and Frank K. Hwang, editors, Computing in Euclidean Geometry, volume 4 of Lecture Notes Series on Computing, pages 47-123. World Scientific, 2nd edition, 1995. Google Scholar
  12. Sergei Bespamyatnikh. An efficient algorithm for enumeration of triangulations. Comput. Geom. Theory and Applications, 23(3):271-279, 2002. URL: http://dx.doi.org/10.1016/S0925-7721(02)00111-6.
  13. Hervé Brönnimann, Lutz Kettner, Michel Pocchiola, and Jack Snoeyink. Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm. SIAM J. Comput., 36(3):721-739, 2006. URL: http://dx.doi.org/10.1137/050631008.
  14. Jérémie Chalopin and Daniel Gonçalves. Every planar graph is the intersection graph of segments in the plane: extended abstract. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 631-638, 2009. URL: http://dx.doi.org/10.1145/1536414.1536500.
  15. Hubert de Fraysseix, János Pach, and Richard Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41-51, 1990. URL: http://dx.doi.org/10.1007/BF02122694.
  16. Q. Ding, J. Qian, W. Tsang, and C. Wang. Randomly generating triangulations of a simple polygon. In Lusheng Wang, editor, Computing and Combinatorics: 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-19, 2005, Proceedings, volume 3595 of Lecture Notes in Computer Science, pages 471-480. Springer, Berlin, 2005. URL: http://dx.doi.org/10.1007/11533719_48.
  17. Adrian Dumitrescu, André Schulz, Adam Sheffer, and Csaba D. Tóth. Bounds on the maximum multiplicity of some common geometric graphs. SIAM J. Discrete Math., 27(2):802-826, 2013. URL: http://dx.doi.org/10.1137/110849407.
  18. Martin Dyer, Leslie Ann Goldberg, and Mike Paterson. On counting homomorphisms to directed acyclic graphs. J. ACM, 54(6):A27:1-A27:23, 2007. URL: http://dx.doi.org/10.1145/1314690.1314691.
  19. Peter Epstein and Jörg-Rüdiger Sack. Generating triangulations at random. ACM Trans. Model. Comput. Simul., 4(3):267-278, 1994. URL: http://dx.doi.org/10.1145/189443.189446.
  20. Philippe Flajolet and Marc Noy. Analytic combinatorics of non-crossing configurations. Discrete Math., 204(1-3):203-229, 1999. URL: http://dx.doi.org/10.1016/S0012-365X(98)00372-0.
  21. Alfredo García, Marc Noy, and Javier Tejel. Lower bounds on the number of crossing-free subgraphs of K_N. Comput. Geom. Theory and Applications, 16(4):211-221, 2000. URL: http://dx.doi.org/10.1016/S0925-7721(00)00010-9.
  22. Ferran Hurtado, Marc Noy, and Jorge Urrutia. Flipping edges in triangulations. Discrete Comput. Geom., 22(3):333-346, 1999. URL: http://dx.doi.org/10.1007/PL00009464.
  23. F. Jaeger, D. L. Vertigan, and D. J. A. Welsh. On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc., 108(1):35-53, 1990. URL: http://dx.doi.org/10.1017/S0305004100068936.
  24. Volker Kaibel and Günter M. Ziegler. Counting lattice triangulations. In C. D. Wensley, editor, Surveys in Combinatorics 2003: Papers from the 19th British Combinatorial Conference held at the University of Wales, Bangor, June 29-July 4, 2003, volume 307 of London Math. Soc. Lecture Note Ser., pages 277-307. Cambridge Univ. Press, Cambridge, UK, 2003. URL: http://arxiv.org/abs/math/0211268.
  25. Pegah Kamousi and Subhash Suri. Stochastic minimum spanning trees and related problems. In Philippe Flajolet and Daniel Panario, editors, Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2011, San Francisco, California, USA, January 22, 2011, pages 107-116. SIAM, 2011. URL: http://dx.doi.org/10.1137/1.9781611973013.12.
  26. Goos Kant and Hans L. Bodlaender. Triangulating planar graphs while minimizing the maximum degree. Inform. and Comput., 135(1):1-14, 1997. URL: http://dx.doi.org/10.1006/inco.1997.2635.
  27. Marek Karpinski, Andrzej Lingas, and Dzmitry Sledneu. A QPTAS for the base of the number of crossing-free structures on a planar point set. Theoretical Computer Science, 711:56-65, 2018. URL: http://dx.doi.org/10.1016/j.tcs.2017.11.003.
  28. Nathan Linial. Hard enumeration problems in geometry and combinatorics. SIAM J. Algebraic Discrete Methods, 7(2):331-335, 1986. URL: http://dx.doi.org/10.1137/0607036.
  29. Anna Lubiw. Decomposing polygonal regions into convex quadrilaterals. In Joseph O'Rourke, editor, Proceedings of the 1st Symposium on Computational Geometry, Baltimore, Maryland, USA, June 5-7, 1985, pages 97-106, New York, 1985. ACM. URL: http://dx.doi.org/10.1145/323233.323247.
  30. Dániel Marx and Tillmann Miltzow. Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems. In Sándor Fekete and Anna Lubiw, editors, Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages A52:1-A52:16, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.52.
  31. Alexander Pilz and Carlos Seara. Convex quadrangulations of bichromatic point sets. In Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG 2017), 2017. URL: https://mat-web.upc.edu/people/carlos.seara/data/publications/internationalConferences/EuroCG-17_paper_23.pdf.
  32. Saurabh Ray and Raimund Seidel. A simple and less slow method for counting triangulations and for related problems. In Proceedings of the 20th European Workshop on Computational Geometry (EuroCG 2004), 2004. URL: https://hdl.handle.net/11441/55368.
  33. Francisco Santos and Raimund Seidel. A better upper bound on the number of triangulations of a planar point set. J. Combin. Theory Ser. A, 102(1):186-193, 2003. URL: http://dx.doi.org/10.1016/S0097-3165(03)00002-5.
  34. Edward R. Scheinerman. Intersection Classes and Multiple Intersection Parameters of Graphs. PhD thesis, Princeton University, 1984. Google Scholar
  35. Walter Schnyder. Embedding planar graphs on the grid. In David S. Johnson, editor, Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990, 22-24 January 1990, San Francisco, California, USA, pages 138-148, 1990. URL: https://dl.acm.org/citation.cfm?id=320176.320191.
  36. Raimund Seidel. On the number of triangulations of planar point sets. Combinatorica, 18(2):297-299, 1998. URL: http://dx.doi.org/10.1007/PL00009823.
  37. Micha Sharir and Adam Sheffer. Counting triangulations of planar point sets. Electron. J. Combin., 18(1):P70:1-P70:74, 2011. URL: https://emis.ams.org/journals/EJC/Volume_18/PDF/v18i1p70.pdf.
  38. Micha Sharir, Adam Sheffer, and Emo Welzl. Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn’s technique. J. Combin. Theory Ser. A, 120(4):777-794, 2013. URL: http://dx.doi.org/10.1016/j.jcta.2013.01.002.
  39. Micha Sharir and Emo Welzl. On the number of crossing-free matchings, cycles, and partitions. SIAM J. Comput., 36(3):695-720, 2006. URL: http://dx.doi.org/10.1137/050636036.
  40. Salil P. Vadhan. The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput., 31(2):398-427, 2001. URL: http://dx.doi.org/10.1137/S0097539797321602.
  41. L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189-201, 1979. URL: http://dx.doi.org/10.1016/0304-3975(79)90044-6.
  42. Manuel Wettstein. Counting and enumerating crossing-free geometric graphs. J. Comput. Geom., 8(1):47-77, 2017. URL: https://jocg.org/index.php/jocg/article/view/280.
  43. Mingji Xia, Peng Zhang, and Wenbo Zhao. Computational complexity of counting problems on 3-regular planar graphs. Theoretical Computer Science, 384(1):111-125, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.05.023.
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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact