zbMATH — the first resource for mathematics

On the number of intersections of two polygons. (English) Zbl 1099.52004
The maximum possible number \(f(k,l)\) of intersections of a simple \(k\)-gon and \(l\)-gon lying in the same plane is known for \(k\geq 3\), \(l\geq 3\) if at least one of the numbers \(k,l\) is even. Namely, \(f(k,l)=kl\) if the both numbers are even and \(f(k,l)=k(l-1)\) if \(k\) is even and \(l\) odd. However, if both \(k\) and \(l\) are odd then only the bounds \(l(k-1)+(3-k)\leq f(k,l)\leq l(k-1)\) are known (for \(k\leq l\)).
The following results are proved in the paper for both \(k\leq l\) being odd:
i) an improved upper bound of \(f(k,l)\) is \(l(k-1)-\lceil \frac {k}{6}\rceil \) for \(k\geq 7\),
ii) if \(l\geq 5\) is odd then \(f(5,l)=4l-2\).
Reviewer: Ivan Saxl (Praha)
52C10 Erdős problems and related topics of discrete geometry
52C45 Combinatorial complexity of geometric structures
Full Text: EuDML EMIS