Let $n\ge 3$ be an integer. An inner diagonal of a simple $n$-gon is a diagonal that is contained in the $n$-gon. Denote by $D(P)$ the number of all inner diagonals of a simple $n$-gon $P$ and by $D(n)$ the least possible value of $D(Q)$, where $Q$ is a simple $n$-gon. Prove that no two inner diagonals of $P$ intersect (except possibly at a common endpoint) if and only if $D(P)=D(n)$. Remark: A simple $n$-gon is a non-self-intersecting polygon with $n$ vertices. A polygon is not necessarily convex.
Problem
Source: MEMO 2015, problem I-2.
Tags: combinatorics, polygon, diagonals, combinatorial geometry
fractals
27.08.2015 20:41
We claim that $D(n) = n - 3$.
The construction is to consider the points $(0, 0), (1, 1), (2, 4), \ldots, (n - 2, (n - 2)^2), (n - 2, 0)$. The idea is, any two points on the parabola will have their diagonal be outside by convexity. So the only interior diagonals are between the last point and the rest, which gives $n - 3$ total interior diagonals, discounting the edges.
To prove it is the minimum, triangulate the polygon. You have at least $n - 3$ interior diagonals right there.
Now we prove the result. If $D(P) = D(n)$, then once you triangulate $P$, that must be all the diagonals. Then no two of them intersect in their strict interiors.
If no two diagonals of $P$ intersect, then once you triangulate $P$, there can be no more diagonals (else they will intersect the triangulation). Then $D(P) = n - 3 = D(n)$.
We are done.
randomusername
27.08.2015 20:44
We use the well-known result that every polygon with $\ge 4$ vertices has an inner diagonal and thus has a triangulation, and this triangulation is composed of $n-2$ triangles, so uses $n-3$ inner diagonals. Because of the existence of this triangulation, $D(n)\ge n-3$. We will later construct an $n$-gon with exactly $n-3$ inner diagonals showing $D(n)=n-3$. Assuming $D(n)=n-3$, an $n$-gon with $D(n)$ inner diagonals can be triangulated with $n-3$ inner diagonals, so there, we have found our $n-3=D(n)$ inner diagonals and they are non-intersecting. Moreover, if no two inner diagonals of an $n$-gon intersect, then there is no inner diagonal other than the $n-3$ inner diagonals composing the triangulation, as it would intersect one of them, so this $n$-gon has $n-3$ inner diagonals. All that is left is the construction. For even $n=2k$, do the following: $\qquad \bullet \quad$ circle $\omega$ has two tangents, $XY_1$ and $XY_k$ with $Y_1,Y_k\in \omega$ $\qquad \bullet \quad$ take $k-1$ points on the arc $Y_1Y_k$ inside triangle $XY_1Y_k$, called $Z_1,Z_2,\dots,Z_{k-1}$ in this order from $Y_1$ to $Y_k$ $\qquad \bullet \quad$ $XZ_1\cap \omega=\{Z_1,X^*\}$ $\qquad \bullet \quad$ take $k-2$ points on the other arc $Y_1Y_k$ between $Y_1$ and $X^*$, namely $Y_2,Y_3,\dots,Y_{k-1}$ $\qquad \bullet \quad$ the $2k$-gon is $XY_1Z_1Y_2Z_2\dots Y_{k-1}Z_{k-1}Y_k$ It is easy to check that then the inner diagonals are precisely $XZ_1,XZ_2,\dots,XZ_{k-1}$ and $Z_1Z_2,Z_2Z_3,\dots,Z_{k-2}Z_{k-1}$, their number is $2k-3$. To achieve a construction for odd $n$, just remove $Y_{k-1}--Z_{k-1}--Y_k$ and replace it with $Y_{k-1}--Y_k$ - this loses a vertex and also a diagonal, so it works.
randomusername
27.08.2015 20:48
Darn sniped, but the above solution is cleaner. Funny how construction+convex=>parabola for me as well, circles were only my second thought. The motivation for mine seems more arcane - it just makes shark teeth polygons precise.
rkm0959
30.08.2016 02:55
Triangulation gives $n + 2D(n) \ge 3(n-2)$, so $D(n) \ge n-3$. For the equality case, there must be a unique triangulation. If $D(n)=n-3$, there is a unique triangulation, so if two inner diagonals intersect, we can swap using those two, a contradiction. Therefore, no two inner diagonals intersect. If no two inner diagonals intersect, if we triangulate the polygon, that is all inner diagonals, so $D(n)=n-3$.