Eyal Ackerman, Balázs Keszegh, and Günter Rote:

An almost optimal bound on the number of intersections of two simple polygons

to appear in: 36th International Symposium on Computational Geometry (SoCG 2020), Zürich, June 2016. Editors: Sergio Cabello and Danny Chen, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020, 18 pages.  →BibTeX


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 even, then every pair of sides may cross and so the answer is mn. If exactly one polygon, say the n-gon, has an odd number of sides, it can intersect each side of the m-gon at most n−1 times; hence there are at most mnm intersections. It is not hard to construct examples that meet these bounds. 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 mn. We prove a new upper bound of mn − (m+n) + C for some constant C, which is optimal apart from the value of C.

  pdf file
other papers about this subject
Last update: February 13, 2020.