On Intersecting Polygons

Abstract

Consider two regions in the plane, bounded by an $n$-gon and an $m$-gon, respectively. At most how many connected components can there be in their intersection? This question was asked by Croft. We answer this asymptotically, proving the bounds $$\lfloor \frac{m}{2}\rfloor \cdot \lfloor \frac{n}{2}\rfloor \le f(n,m)\le \lfloor \frac{m}{2}\rfloor \cdot \frac{n}{2}+\frac{m}{2}$$ where $f(n,m)$ denotes the maximal number of components and $m\le n$. Furthermore, we give an exact answer to the related question of finding the maximal number of components if the $m$-gon is required to be convex: $\lfloor \frac{m+n-2}{2}\rfloor$ if $n\ge m+2$ and $n-2$ otherwise.