We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons.
- Authors
Ackerman, Eyal; Keszegh, Balázs; Rote, Günter
- Abstract
What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even: If both m and n are even, then every pair of sides may cross and so the answer is mn. If exactly one polygon, say the n-gon, has an odd number of sides, it can intersect each side of the m-gon polygon at most n - 1 times; hence there are at most m n - m intersections. It is not hard to construct examples that meet these bounds. If both m and n are odd, the best known construction has m n - (m + n) + 3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only m n - (m + ⌈ n / 6 ⌉) , for m ≥ n . We prove a new upper bound of m n - (m + n) + C for some constant C, which is optimal apart from the value of C.
- Subjects
INTERSECTION numbers; ODD numbers; RAMSEY theory; POLYGONS
- Publication
Discrete & Computational Geometry, 2022, Vol 68, Issue 4, p1049
- ISSN
0179-5376
- Publication type
Article
- DOI
10.1007/s00454-022-00438-0