17

This question is a follow-up to Maximum number of intersections between a quadrilateral and a pentagon, where it is shown that the boundaries $\partial Q,\partial P$ of a quadrilateral and a pentagon in the plane cannot intersect at more than $16$ points, since each side of $\partial Q$ meets $\partial P$ at an even number of points.

Q: Given the boundaries $\partial P_1, \partial P_2$ of two pentagons in the plane, is it possible that $$ \left|\partial P_1 \cap \partial P_2 \right| = 20?$$

Each side of $\partial P_1$ meets $\partial P_2$ at an even number of points, so equality is attained iff there is some configuration such that each side of $\partial P_1$ meets each side of $\partial P_2$ except one. $\left|\partial P_1 \cap \partial P_2\right| = 18$ is possible, as shown below, enter image description here

and I believe that $\left|\partial P_1 \cap \partial P_2\right| = 20$ is impossible, but I am failing to prove it.

Jack D'Aurizio
  • 348,665
  • 41
  • 374
  • 814

1 Answers1

10

According to Theorem 4 from Černy et al.'s "On the number of intersections of two polygons" (2003), the number of intersections is bounded by $$5\times 5-\left\lceil \frac56 \right\rceil-5=19$$ Therefore $18$ is the maximum.

Alternatively, Theorem 5 gives the exact value $4\times 5-2=18$.

These maximal intersection numbers are hard to compute when both polygons have an odd number of vertices. Otherwise there are general formulas given by Theorem 1 and 2.

Edit: found a better result in Günther's "The maximum number of intersections of two polygons" (2012).

Theorem: the maximal number of intersections between an $n$-polygon and an $m$-polygon with $n$ and $m$ both odd is $(n-1)(m-1)+2$.

Arnaud Mortier
  • 26,904
  • 3
  • 32
  • 81