Document Open Access Logo

A Superlinear Lower Bound on the Number of 5-Holes

Authors Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kyncl, Irene Parada, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.8.pdf
  • Filesize: 0.57 MB
  • 16 pages

Document Identifiers

Author Details

Oswin Aichholzer
Martin Balko
Thomas Hackl
Jan Kyncl
Irene Parada
Manfred Scheucher
Pavel Valtr
Birgit Vogtenhuber

Cite As Get BibTex

Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kyncl, Irene Parada, Manfred Scheucher, Pavel Valtr, and Birgit Vogtenhuber. A Superlinear Lower Bound on the Number of 5-Holes. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.8

Abstract

Let P be a finite set of points in the plane in general position, that is, no three points of P are on a common line. We say that a set H of five points from P is a 5-hole in P if H is the vertex set of a convex 5-gon containing no other points of P. For a positive integer n, let h_5(n) be the minimum number of 5-holes among all sets of n points in the plane in general position.

Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for h_5(n) have been of order Omega(n) and O(n^2), respectively. We show that h_5(n) = Omega(n(log n)^(4/5)), obtaining the first superlinear lower bound on h_5(n).

The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set P of points in the plane in general position is partitioned by a line l into two subsets, each of size at least 5 and not in convex position, then l intersects the convex hull of some 5-hole in P. The proof of this result is computer-assisted.

Subject Classification

Keywords
  • Erdös-Szekeres type problem
  • k-hole
  • empty k-gon
  • empty pentagon
  • planar point set

Metrics

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

References

  1. O. Aichholzer. Enumerating order types for small point sets with applications. URL: http://www.ist.tugraz.at/aichholzer/research/rp/triangulations/ordertypes/.
  2. O. Aichholzer. [Empty] [colored] k-gons. Recent results on some Erdős-Szekeres type problems. In Proceedings of XIII Encuentros de Geometría Computacional, pages 43-52, Zaragoza, Spain, 2009. Google Scholar
  3. O. Aichholzer, F. Aurenhammer, and H. Krasser. Enumerating order types for small point sets with applications. Order, 19(3):265-281, 2002. Google Scholar
  4. O. Aichholzer, M. Balko, T. Hackl, J. Kynčl, I. Parada, M. Scheucher, P. Valtr, and B. Vogtenhuber. A superlinear lower bound on the number of 5-holes. http://arXiv.org/abs/1703.05253, 2017.
  5. O. Aichholzer, R. Fabila-Monroy, T. Hackl, C. Huemer, A. Pilz, and B. Vogtenhuber. Lower bounds for the number of small convex k-holes. Computational Geometry: Theory and Applications, 47(5):605-613, 2014. Google Scholar
  6. O. Aichholzer, T. Hackl, and B. Vogtenhuber. On 5-gons and 5-holes. Lecture Notes in Computer Science, 7579:1-13, 2012. Google Scholar
  7. O. Aichholzer and H. Krasser. Abstract order type extension and new results on the rectilinear crossing number. Computational Geometry: Theory and Applications, 36(1):2-15, 2007. Google Scholar
  8. M. Balko. URL: http://kam.mff.cuni.cz/~balko/superlinear5Holes.
  9. M. Balko, R. Fulek, and J. Kynčl. Crossing numbers and combinatorial characterization of monotone drawings of K_n. Discrete &Computational Geometry, 53(1):107-143, 2015. Google Scholar
  10. I. Bárány and Z. Füredi. Empty simplices in Euclidean space. Canadian Mathematical Bulletin, 30(4):436-445, 1987. Google Scholar
  11. I. Bárány and Gy. Károlyi. Problems and results around the Erdős-Szekeres convex polygon theorem. In Akiyama, Kano, and Urabe, editors, Discrete and Computational Geometry, volume 2098 of Lecture Notes in Computer Science, pages 91-105. Springer, 2001. Google Scholar
  12. I. Bárány and P. Valtr. Planar point sets with a small number of empty convex polygons. Studia Scientiarum Mathematicarum Hungarica, 41(2):243-266, 2004. Google Scholar
  13. P. Brass, W. Moser, and J. Pach. Research Problems in Discrete Geometry. Springer, 2005. Google Scholar
  14. K. Dehnhardt. Leere konvexe Vielecke in ebenen Punktmengen. PhD thesis, TU Braunschweig, Germany, 1987. In German. Google Scholar
  15. P. Erdős. Some more problems on elementary geometry. Australian Mathematical Society Gazette, 5(2):52-54, 1978. Google Scholar
  16. P. Erdős and G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463-470, 1935. Google Scholar
  17. S. Felsner and H. Weil. Sweeps, arrangements and signotopes. Discrete Applied Mathematics, 109(1-2):67-94, 2001. Google Scholar
  18. A. García. A note on the number of empty triangles. Lecture Notes in Computer Science, 7579:249-257, 2012. Google Scholar
  19. T. Gerken. Empty convex hexagons in planar point sets. Discrete & Computational Geometry, 39(1-3):239-272, 2008. Google Scholar
  20. J. E. Goodman and R. Pollack. Multidimensional sorting. SIAM Journal on Computing, 12(3):484-507, 1983. Google Scholar
  21. H. Harborth. Konvexe Fünfecke in ebenen Punktmengen. Elemente der Mathematik, 33:116-118, 1978. In German. Google Scholar
  22. J. D. Horton. Sets with no empty convex 7-gons. Canadian Mathematical Bulletin, 26(4):482-484, 1983. Google Scholar
  23. C. M. Nicolás. The empty hexagon theorem. Discrete & Computational Geometry, 38(2):389-397, 2007. Google Scholar
  24. R. Pinchasi, R. Radoičić, and M. Sharir. On empty convex polygons in a planar point set. Journal of Combinatorial Theory, Series A, 113(3):385-419, 2006. Google Scholar
  25. M. Scheucher. URL: http://www.ist.tugraz.at/scheucher/5holes.
  26. M. Scheucher. Counting convex 5-holes, Bachelor’s thesis, 2013. In German. Google Scholar
  27. M. Scheucher. On order types, projective classes, and realizations, Bachelor’s thesis, 2014. Google Scholar
  28. W. Steiger and J. Zhao. Generalized ham-sandwich cuts. Discrete &Computational Geometry, 44(3):535-545, 2010. Google Scholar
  29. P. Valtr. Convex independent sets and 7-holes in restricted planar point sets. Discrete & Computational Geometry, 7(2):135-152, 1992. Google Scholar
  30. P. Valtr. Sets in ℝ^d with no large empty convex subsets. Discrete Mathematics, 108(1):115-124, 1992. Google Scholar
  31. P. Valtr. On empty pentagons and hexagons in planar point sets. In Proceedings of Computing: The Eighteenth Australasian Theory Symposium (CATS 2012), pages 47-48, Melbourne, Australia, 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact