Document Open Access Logo

Chains, Koch Chains, and Point Sets with Many Triangulations

Authors Daniel Rutschmann, Manuel Wettstein

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.59.pdf
  • Filesize: 0.68 MB
  • 18 pages

Document Identifiers

Author Details

Daniel Rutschmann
  • Department of Computer Science, ETH Zürich, Switzerland
Manuel Wettstein
  • Department of Computer Science, ETH Zürich, Switzerland

Acknowledgements

The material presented in this paper originates from the first author’s Master’s thesis [Rutschmann, 2021] under the second author’s direct supervision. Both authors wish to express their gratitude to Emo Welzl, the official advisor in this endeavor.

Cite AsGet BibTex

Daniel Rutschmann and Manuel Wettstein. Chains, Koch Chains, and Point Sets with Many Triangulations. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.59

Abstract

We introduce the abstract notion of a chain, which is a sequence of n points in the plane, ordered by x-coordinates, so that the edge between any two consecutive points is unavoidable as far as triangulations are concerned. A general theory of the structural properties of chains is developed, alongside a general understanding of their number of triangulations. We also describe an intriguing new and concrete configuration, which we call the Koch chain due to its similarities to the Koch curve. A specific construction based on Koch chains is then shown to have Ω(9.08ⁿ) triangulations. This is a significant improvement over the previous and long-standing lower bound of Ω(8.65ⁿ) for the maximum number of triangulations of planar point sets.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Planar Point Set
  • Chain
  • Koch Chain
  • Triangulation
  • Maximum Number of Triangulations
  • Lower Bound

Metrics

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

Related Versions

References

  1. OEIS Foundation Inc. (2021). The on-line encyclopedia of integer sequences. Catalan numbers. URL: https://oeis.org/A000108.
  2. OEIS Foundation Inc. (2021). The on-line encyclopedia of integer sequences. Large Schröder numbers. URL: https://oeis.org/A006318.
  3. OEIS Foundation Inc. (2021). The on-line encyclopedia of integer sequences. Little Schröder numbers. URL: https://oeis.org/A001003.
  4. Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann, and Birgit Vogtenhuber. An improved lower bound on the minimum number of triangulations. In Proceedings of the 32nd International Symposium on Computational Geometry, 2016. URL: https://doi.org/10.4230/LIPIcs.SoCG.2016.7.
  5. Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser, and Birgit Vogtenhuber. On the number of plane geometric graphs. Graphs Comb., 23(Supplement-1):67-84, 2007. URL: https://doi.org/10.1007/s00373-007-0704-5.
  6. Miklós Ajtai, Václav Chvátal, Monroe M. Newborn, and Endre Szemerédi. Crossing-free subgraphs. In Theory and Practice of Combinatorics, volume 60 of North-Holland Mathematics Studies, pages 9-12. North-Holland, 1982. Google Scholar
  7. Victor Alvarez and Raimund Seidel. A simple aggregative algorithm for counting triangulations of planar point sets and related problems. In Proceedings of the 29th the Symposium on Computational Geometry, 2013. URL: https://doi.org/10.1145/2462356.2462392.
  8. Andrei Asinowski, Christian Krattenthaler, and Toufik Mansour. Counting triangulations of some classes of subdivided convex polygons. Eur. J. Comb., 62:92-114, 2017. URL: https://doi.org/10.1016/j.ejc.2016.12.002.
  9. David Avis and Komei Fukuda. Reverse search for enumeration. Discret. Appl. Math., 65(1-3):21-46, 1996. URL: https://doi.org/10.1016/0166-218X(95)00026-N.
  10. Sergei Bespamyatnikh. An efficient algorithm for enumeration of triangulations. Comput. Geom., 23(3):271-279, 2002. URL: https://doi.org/10.1016/S0925-7721(02)00111-6.
  11. Markus Denny and Christian Sohler. Encoding a triangulation as a permutation of its point set. In Proceedings of the 9th Canadian Conference on Computational Geometry, 1997. Google Scholar
  12. Adrian Dumitrescu, André Schulz, Adam Sheffer, and Csaba D. Tóth. Bounds on the maximum multiplicity of some common geometric graphs. SIAM J. Discret. Math., 27(2):802-826, 2013. URL: https://doi.org/10.1137/110849407.
  13. Peter Epstein and Jörg-Rüdiger Sack. Generating triangulations at random. ACM Trans. Model. Comput. Simul., 4(3):267-278, 1994. URL: https://doi.org/10.1145/189443.189446.
  14. Jacob E. Goodman and Richard Pollack. Multidimensional sorting. SIAM J. Comput., 12(3):484-507, 1983. URL: https://doi.org/10.1137/0212032.
  15. Ferran Hurtado and Marc Noy. Counting triangulations of almost-convex polygons. Ars Comb., 45, 1997. Google Scholar
  16. Dániel Marx and Tillmann Miltzow. Peeling and nibbling the cactus: Subexponential-time algorithms for counting triangulations and related problems. In Proceedings of the 32nd International Symposium on Computational Geometry, 2016. URL: https://doi.org/10.4230/LIPIcs.SoCG.2016.52.
  17. Alfredo García Olaverri, Marc Noy, and Javier Tejel. Lower bounds on the number of crossing-free subgraphs of k_n. Comput. Geom., 16(4):211-221, 2000. URL: https://doi.org/10.1016/S0925-7721(00)00010-9.
  18. Daniel Rutschmann. On chains and point configurations with many triangulations. Master’s thesis, ETH Zurich, Zürich, Switzerland, 2021. Google Scholar
  19. Francisco Santos and Raimund Seidel. A better upper bound on the number of triangulations of a planar point set. J. Comb. Theory, Ser. A, 102(1):186-193, 2003. URL: https://doi.org/10.1016/S0097-3165(03)00002-5.
  20. Raimund Seidel. On the number of triangulations of planar point sets. Comb., 18(2):297-299, 1998. URL: https://doi.org/10.1007/PL00009823.
  21. Micha Sharir and Adam Sheffer. Counting triangulations of planar point sets. Electron. J. Comb., 18(1), 2011. URL: http://www.combinatorics.org/Volume_18/Abstracts/v18i1p70.html.
  22. Micha Sharir and Emo Welzl. Random triangulations of planar point sets. In Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006. URL: https://doi.org/10.1145/1137856.1137898.
  23. Warren D. Smith. Studies in Computational Geometry Motivated by Mesh Generation. PhD thesis, Princeton University, Princeton, USA, 1989. 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact