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-\left\lceil k/6\right\rceil-l$ and obtain exact bounds for $k=5$ $(f(5,l)=4l-2)$ in this case.
@article{119381,
author = {Jakub \v Cern\'y and Jan K\'ara and Daniel Kr\'al' and Pavel Podbrdsk\'y and Miroslava Sot\'akov\'a and Robert \v S\'amal},
title = {On the number of intersections of two polygons},
journal = {Commentationes Mathematicae Universitatis Carolinae},
volume = {44},
year = {2003},
pages = {217-228},
zbl = {1099.52004},
mrnumber = {2026159},
language = {en},
url = {http://dml.mathdoc.fr/item/119381}
}
Černý, Jakub; Kára, Jan; Král', Daniel; Podbrdský, Pavel; Sotáková, Miroslava; Šámal, Robert. On the number of intersections of two polygons. Commentationes Mathematicae Universitatis Carolinae, Tome 44 (2003) pp. 217-228. http://gdmltest.u-ga.fr/item/119381/
The common exterior of convex polygons in the plane, Comput. Geom. 8 (3) (1997), 139-149. (1997) | MR 1467119 | Zbl 0881.68122
On The Maximum Number of Intersections of Two Polyhedra in 2 and 3 Dimensions, Proceedings of the Fifth Canadian Conference on Computational Geometry, Waterloo, Ontario, August, 1993, pp.49-54.
On the complexity of the union of fat convex objects in the plane, Discrete Comput. Geom. 23 (2000), 171-189. (2000) | MR 1739604 | Zbl 0944.68183
Selfintersections of polygons, Geombinatorics 8 (1998), 2 37-45. (1998) | MR 1647013
On fat partitioning, fat covering and the union size of polygons, Comput. Geom. 9 (1994), 4 197-210. (1994) | MR 1609598
Fat triangles determine linearly many holes, SIAM J. Comput. 23 (1994), 1 154-169. (1994) | MR 1259000
On the boundary of the union of planar convex sets, Discrete Comput. Geom. 3 (1999), 321-328. (1999) | MR 1672968 | Zbl 0927.52001