Maximum number of intersections between two simple heptagons
Let denote the maximum number of distinct intersection points between the boundaries of two simple polygons with and sides in the plane, restricted to pairs whose boundary intersection is finite.
The polygons need not be convex or in general position. Shared vertices, vertex–side contacts, and tangential contacts are allowed, and each distinct intersection point is counted once. Overlapping boundary segments are excluded by the finiteness requirement.
Problem. Determine the exact value of . In particular, is
The conjectured formula for odd is
which predicts 38 for two heptagons. A construction with 38 transverse boundary intersections is known, so the question is whether any pair of simple heptagons with finitely many boundary intersections can exceed this number.
For pairs in general position, the upper bound of Černý et al. gives at most 40 intersections. Since transverse crossings of two simple closed curves occur in even numbers, the general-position case reduces to excluding 40 crossings. Extending a bound from general position to the full problem also requires a reduction that preserves simplicity and does not decrease the number of distinct boundary intersection points; degeneracies are addressed in §9 of the journal version of Ackerman–Keszegh–Rote.
References
References
Michael B. Dillencourt, David M. Mount, and Alan Saalfeld. “On the Maximum Number of Intersections of Two Polyhedra in 2 and 3 Dimensions.” Proceedings of the 5th Canadian Conference on Computational Geometry, pp. 49–54, 1993.
Jakub Černý, Jan Kára, Daniel Král’, Pavel Podbrdský, Miroslava Sotáková, and Robert Šámal. “On the Number of Intersections of Two Polygons.” Commentationes Mathematicae Universitatis Carolinae 44(2), pp. 217–228, 2003.
Eyal Ackerman, Balázs Keszegh, and Günter Rote. “An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons.” Discrete & Computational Geometry 68(4), pp. 1049–1077, 2022. Journal version; §9 addresses the removal of degeneracies.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.