## 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
### 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 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
`m``n`−`m` intersections. It is not hard to construct examples that meet
these bounds. If both `m` and `n` are odd, the best known
construction has `m``n`−(`m`+`n`)+3
intersections, and it is conjectured
that this is the maximum. However, the best known upper bound is only
`m``n` − (`m`+⌈`n`/6⌉), for `m`≥`n`. We prove a new upper
bound of `m``n` − (`m`+`n`) + `C` for some constant `C`, which is
optimal apart from the value of `C`.

Last update: February 13, 2020.