Document Open Access Logo

An Improved Lower Bound on the Minimum Number of Triangulations

Authors Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann, Birgit Vogtenhuber

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.7.pdf
  • Filesize: 0.72 MB
  • 16 pages

Document Identifiers

Author Details

Oswin Aichholzer
Victor Alvarez
Thomas Hackl
Alexander Pilz
Bettina Speckmann
Birgit Vogtenhuber

Cite As Get BibTex

Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann, and Birgit Vogtenhuber. An Improved Lower Bound on the Minimum Number of Triangulations. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.7

Abstract

Upper and lower bounds for the number of geometric graphs of specific types on a given set of points in the plane have been intensively studied in recent years. For most classes of geometric graphs it is now known that point sets in convex position minimize their number. However, it is still unclear which point sets minimize the number of geometric triangulations;  the so-called double circles are conjectured to be the minimizing sets. In this paper we prove that any set of n points in general position in the plane has at least Omega(2.631^n) geometric triangulations. Our result improves the previously best general lower bound of Omega(2.43^n) and also covers the previously best lower bound of Omega(2.63^n) for a fixed number of extreme points. We achieve our bound by showing and combining several new results, which are of independent interest:
(1) Adding a point on the second convex layer of a given point set (of 7 or more points) at least doubles the number of triangulations.
(2) Generalized configurations of points that minimize the number of triangulations have at most n/2 points on their convex hull.
(3) We provide tight lower bounds for the number of triangulations of point sets with up to 15 points. These bounds further support the double circle conjecture.

Subject Classification

Keywords
  • Combinatorial geometry
  • Order types
  • Triangulations

Metrics

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

References

  1. Oswin Aichholzer, Franz Aurenhammer, and Hannes Krasser. Enumerating order types for small point sets with applications. Order, 19(3):265-281, 2002. URL: http://dx.doi.org/10.1023/A:1021231927255.
  2. Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser, and Birgit Vogtenhuber. On the number of plane geometric graphs. Graphs Combin., 23: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., 29(2):135-145, 2004. Google Scholar
  4. Oswin Aichholzer and Hannes Krasser. Abstract order type extension and new results on the rectilinear crossing number. Comput. Geom., 36(1):2-15, 2007. Google Scholar
  5. Selim G. Akl. A lower bound on the maximum number of crossing-free Hamiltonian cycles in a rectilinear drawing of K_n. Ars Combin., 7:7-18, 1979. Google Scholar
  6. 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. Google Scholar
  7. Victor Alvarez and Raimund Seidel. A simple aggregative algorithm for counting triangulations of planar point sets and related problems. In Proc. 29th Annual Symposium on Computational Geometry (SoCG 2013), pages 1-8. ACM, 2013. Google Scholar
  8. Adrian Dumitrescu, André Schulz, Adam Sheffer, and Csaba D. Tóth. Bounds on the maximum multiplicity of some common geometric graphs. SIAM Journal on Discrete Mathematics, 27(2):802-826, 2013. Google Scholar
  9. Jacob E. Goodman. Proof of a conjecture of Burr, Grünbaum, and Sloane. Discrete Math., 32(1):27-35, 1980. URL: http://dx.doi.org/10.1016/0012-365X(80)90096-5.
  10. Jacob E. Goodman and Richard Pollack. Proof of Grünbaum’s conjecture on the stretchability of certain arrangements of pseudolines. J. Comb. Theory, Ser. A, 29(3):385-390, 1980. URL: http://dx.doi.org/10.1016/0097-3165(80)90038-2.
  11. Jacob E. Goodman and Richard Pollack. Multidimensional sorting. SIAM J. Comput., 12(3):484-507, 1983. Google Scholar
  12. Jacob E. Goodman and Richard Pollack. Semispaces of configurations, cell complexes of arrangements. J. Comb. Theory, Ser. A, 37(3):257-293, 1984. Google Scholar
  13. Michael Hoffmann, André Schulz, Micha Sharir, Adam Sheffer, Csaba D. Tóth, and Emo Welzl. Thirty Essays on Geometric Graph Theory, chapter Counting Plane Graphs: Flippability and Its Applications, pages 303-325. Springer New York, New York, NY, 2013. Google Scholar
  14. Hannes Krasser. Order Types of Point Sets in the Plane. PhD thesis, Institute for Theoretical Computer Science, Graz University of Technology, October 2003. Google Scholar
  15. Paul McCabe and Raimund Seidel. New lower bounds for the number of straight-edge triangulations of a planar point set. In Proc. 20th European Workshop on Computational Geometry (EWCG 2004), pages 175-176, 2004. Google Scholar
  16. Alexander Pilz and Emo Welzl. Order on order types. In Proc. 31st Int. Symposium on Computational Geometry (SoCG 2015), volume 34 of LIPIcs, pages 285-299, 2015. Google Scholar
  17. Saurabh Ray and Raimund Seidel. A simple and less slow method for counting triangulations and for related problems. In Proc. 20th European Workshop on Computational Geometry (EWCG 2004), pages 177-180, 2004. Google Scholar
  18. Andreas Razen, Jack Snoeyink, and Emo Welzl. Number of crossing-free geometric graphs vs. triangulations. Electr. Notes Discrete Math., 31:195-200, 2008. 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. Google Scholar
  20. Micha Sharir and Adam Sheffer. Counting triangulations of planar point sets. Electr. J. Comb., 18(1), 2011. Google Scholar
  21. Micha Sharir and Adam Sheffer. Counting plane graphs: Cross-graph charging schemes. Combinatorics, Probability & Computing, 22(6):935-954, 2013. Google Scholar
  22. Micha Sharir, Adam Sheffer, and Emo Welzl. On degrees in random triangulations of point sets. J. Comb. Theory, Ser. A, 118(7):1979-1999, 2011. 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 About DROPS Imprint Privacy Contact