Geodesic
On the number of intersections of two polygons
Commentationes Mathematicae Universitatis Carolinae, Tome 44 (2003) no. 2, pp. 217-228

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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.
Classification : 52C10, 52C45
Keywords: geometry; polygon; intersection; combinatorial complexity 
@article{CMUC_2003__44_2_a2,
     author = {\v{C}ern\'y, Jakub and K\'ara, Jan and Kr\'al', Daniel and Podbrdsk\'y, Pavel and Sot\'akov\'a, Miroslava and \v{S}\'amal, Robert},
     title = {On the number of intersections of two polygons},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {217--228},
     publisher = {mathdoc},
     volume = {44},
     number = {2},
     year = {2003},
     mrnumber = {2026159},
     zbl = {1099.52004},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_2003__44_2_a2/}
}
TY  - JOUR
AU  - Černý, Jakub
AU  - Kára, Jan
AU  - Král', Daniel
AU  - Podbrdský, Pavel
AU  - Sotáková, Miroslava
AU  - Šámal, Robert
TI  - On the number of intersections of two polygons
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 2003
SP  - 217
EP  - 228
VL  - 44
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CMUC_2003__44_2_a2/
LA  - en
ID  - CMUC_2003__44_2_a2
ER  - 
%0 Journal Article
%A Černý, Jakub
%A Kára, Jan
%A Král', Daniel
%A Podbrdský, Pavel
%A Sotáková, Miroslava
%A Šámal, Robert
%T On the number of intersections of two polygons
%J Commentationes Mathematicae Universitatis Carolinae
%D 2003
%P 217-228
%V 44
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CMUC_2003__44_2_a2/
%G en
%F CMUC_2003__44_2_a2
Č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) no. 2, pp. 217-228. http://geodesic.mathdoc.fr/item/CMUC_2003__44_2_a2/