Jakub \v Cern\'y, Jan K\'ara, Daniel Kr\'al', Pavel Podbrdsk\'y, Miroslava Sot\'akov\'a, Robert \v S\'amal
On the number of intersections of two polygons

Comment.Math.Univ.Carolinae 44,2 (2003) 217-228.

Abstract:We study the maximum possible number $f(k,l)$ of intersections of the boundaries of a simple $k$-gon with a simple $l$-gon in the plane for $k,l\ge 3$. To determine the number $f(k,l)$ is quite easy and known when $k$ or $l$ is even but still remains open for $k$ and $l$ both odd. We improve (for $k\le l$) the easy upper bound $kl-l$ to $kl-\ceil {k/6}-l$ and obtain exact bounds for $k=5$ $(f(5,l)=4l-2)$ in this case.

Keywords: geometry, polygon, intersection, combinatorial complexity
AMS Subject Classification: 52C45, 52C10

PDF