Document Open Access Logo

An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons

Authors Eyal Ackerman, Balázs Keszegh , Günter Rote

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.1.pdf
  • Filesize: 1.28 MB
  • 18 pages

Document Identifiers

Author Details

Eyal Ackerman
  • Department of Mathematics, Physics, and Computer Science, University of Haifa at Oranim, Tivon 36006, Israel
Balázs Keszegh
  • Alfréd Rényi Institute of Mathematics, H-1053 Budapest, Hungary
  • MTA-ELTE Lendület Combinatorial Geometry Research Group, Budapest, Hungary
Günter Rote
  • Department of Computer Science, Freie Universität Berlin, Takustr. 9, 14195 Berlin, Germany

Funding

  • Ackerman, Eyal: The main part of this work was performed during a visit to Freie Universität Berlin which was supported by the Freie Universität Alumni Program.
  • Keszegh, Balázs: Research supported by the Lendület program of the Hungarian Academy of Sciences (MTA), under the grant LP2017-19/2017 and by the National Research, Development and Innovation Office - NKFIH under the grant K 116769.

Acknowledgements

We thank the reviewers for helpful suggestions.

Cite AsGet BibTex

Eyal Ackerman, Balázs Keszegh, and Günter Rote. An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.1

Abstract

What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even. If both m and n are odd, the best known construction has mn-(m+n)+3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only mn-(m + ⌈ n/6 ⌉), for m ≥ n. We prove a new upper bound of mn-(m+n)+C for some constant C, which is optimal apart from the value of C.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Combinatoric problems
Keywords
  • Simple polygon
  • Ramsey theory
  • combinatorial geometry

Metrics

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

Related Versions

References

  1. J. Černý, J. Kára, D. Král', P. Podbrdský, M. Sotáková, and R. Šámal. On the number of intersections of two polygons. Comment. Math. Univ. Carolinae, 44(2):217-228, 2003. URL: https://cmuc.karlin.mff.cuni.cz/cmuc0302/cmuc0302.htm.
  2. Michael B. Dillencourt, David M. Mount, and Alan Saalfeld. On the maximum number of intersections of two polyhedra in 2 and 3 dimensions. In Proceedings of the 5th Canadian Conference on Computational Geometry, Waterloo, Ontario, Canada, August 1993, pages 49-54. University of Waterloo, 1993. Google Scholar
  3. P. Erdős and L. Moser. On the representation of directed graphs as unions of orderings. Magyar Tud. Akad. Mat. Kutató Int. Közl., 9:125-132, 1964. Google Scholar
  4. P. Erdős and G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463-470, 1935. Google Scholar
  5. Felix Günther. The maximum number of intersections of two polygons, July 2012. withdrawn by the author. URL: http://arxiv.org/abs/1207.0996.
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