Covering a polygon with an odd number of sides

Solution 1:

The statement is true. In fact, we can generalize it a little bit beyond the simple polygons; we need only the weaker condition that its winding number is $1$ (intuitively, that if you "walk around" the polygon you will only make a turn of $360^\circ$, not any other multiple thereof - its angles add up to the right amount). We can also bend the edges however we like.

To see that it doesn't necessarily hold for polygons with higher winding number, consider the case of a 5-pointed star (darker regions indicating those which are swept out twice):

To answer the question, we move from the discrete to the continuous and solve a more generalized problem.

Claim: Let $C$ be a closed curve given by a map $f:[0,1]\to \mathbb{R}^2$ such that $f(0)=f(1)$, and for notational convenience let $f(x)$ denote $f(x\pmod{1})$ in the event that $x\not\in[0,1]$. We wish to show that the union of the line segments connecting $f(x)$ and $f(x+0.5)$ for every $x\in[0,1]$ contains every point around which $C$ has winding number $1$. (Intuitively, this just means that if you stood at that point and turned to watch the path of $C$ from $f(0)$ to $f(1)$, you would make one turn counterclockwise.)

First, let's see that the claim implies our proposition. Given a polygon $\mathscr{P}$ as in the problem with $2k+1$ vertices $P_1,\ldots,P_{2k+1}$, we partition $[0,1]$ into $4k+2$ equal intervals $I_1,I_2,\ldots,I_{4k+2}$, and define $f$ so that for $x\in I_{2j}$, $f(x)$ is constant at the point $P_j$. For $x\in I_{2j+1}$, $f(x)$ traverses the edge from $P_j$ to $P_{j+1}$ (let's say linearly, but any continuous parameterization works). Now, observe that $f$ is indeed a continuous function with $f(0)=f(1)=P_{2k+1}$, and that the curve $C$ is our polygon. Note also that if you are standing in the interior of a simple polygon, it will make a net revolution of $2\pi$ radians around you, which we can choose to be counterclockwise by reversing the order of the vertices (or flipping the signs on this proof - the sign of the winding number doesn't matter, I'm just taking it to be positive for convenience).

Finally, note that as $x$ ranges over the interval $I_{2j}$, the locus of all these line segments is exactly the triangle formed by vertex $P_j$ and its "opposite side" $\overline{P_{j+k}P_{j+k+1}}$ (where the indices are to be interpreted modulo $2k+1$). (When $x$ is in an odd-indexed interval,$x+0.5$ is in an even-indexed one, so these triangles cover every line segment involved.)

So, for the given parameterization, this just says that every point in the interior of the polygon $\mathscr{P}$ is covered by one of these triangles.

Having established that the claim will yield what we want, we move on to the proof.

Proof of claim: Let $q$ be a point not on $C$. Then we can associate each point $f(t)\in C$ with an angle $\theta(t)$ of the vector from $q$ to $f(t)$, parametrized in the usual way relative to the positive $x$-axis (but where we only care about the value modulo $2\pi$).

By some basic covering space theory (I think the Wikipedia article on the winding number sketches this out in more formality), we can uniquely choose the multiple-of-$2\pi$ offsets of $\theta(t)$ so that $\theta(t)$ is continuous and $\theta(0)=0$. $q$ has winding number $1$ iff $\theta(1)=2\pi$. As an example: if $q$ is the origin and $f(t)=(\cos(2\pi t), \sin(2\pi t))$, then $\theta(t)=2\pi t$.

Now, observe that if $\theta(s)-\theta(t)\equiv\pi\equiv-\pi\pmod{2\pi}$, the line segment from $f(s)$ to $f(t)$ contains $q$.

Now, consider $g(t)=\theta(t+0.5)-\theta(t)$. $g$ is a continuous function on $[0,0.5]$, and $g(0)+g(0.5)=\theta(1)-\theta(0)=2\pi$ by assumption on $q$, so by the Intermediate Value Theorem $g$ takes on the value $\pi$ at some point. But this is exactly the condition we need for $q$ to be in our locus of line segments, completing the proof.

(Thanks to Calvin Lin for the "beam" framing of the problem, and thinking about things in terms of a rotating line segment instead of a sum of triangles.)

Solution 2:

For convex polygons, I believe the answer is true. You can use ideas similar to the IMO Windmill problem (2011/2).

First, instead of considering the central triangles, we consider a BEAM that goes through a vertex $P$, splits the remaining vertices into two sets of equal size, rotates clockwise while pivoting around the vertex $P$ until it hits another vertex $Q$. This vertex takes over as the new pivot and continues rotating clockwise. This process continues indefinitely, cycling through all of the vertices.

Number the vertices $1, 2, \ldots 2k+1$ in a clockwise manner.

Claim: When the beams is only going through one vertex, then it splits the remaining vertices evenly.
Proof: The number of vertices that are on one side of the beam is an invariant prior to and after connecting with the next pivot. The result follows.

Claim: If the beam is pivoting about vertex $v$, then the next pivot will be $v-k$.
Proof: Because the polygon is convex, the vertices $v-k$ and $v+k = v-k-1$ uniquely satisfy "split the remaining vertices evenly just prior to and after connecting with the next pivot". Due to the clockwise ordering, the sequence is $v-k-1 \rightarrow v \rightarrow v-1$.

Claim: The area within the polygon which the beam covers, is indeed the union of the central triangle.
Proof: With the pivot at vertex indexed $v$, the prior vertex is $v-k-1$ and the next vertex is $v-k$, so the beam's intersection with the polygon is the triangle $v-k-1, v , v-k$.

Claim: Every point in the convex polygon is covered by this beam (at least once).
Proof: Consider a point $p$ in the polygon that doesn't lie on any diagonal.
Draw a line through this point $p$, and let it pivot about $p$.
As this line pivots about $p$, when the line intersects a vertex, count the number of vertices to the "left" of the line and to the "right" of the line.
When the line pivots $180^\circ$, these two numbers flip over. Consider the expression "left vertices minus right vertices". It

• has even parity,
• changes by exactly 2 each time the line goes through a vertex
• changes signage after a $180^\circ$ rotation.

Hence, by "continuity" (applied to the discrete change), it must be equal to 0 after some rotation. Let this vertex be $K$. Then, from the above, the vertex is covered by the central triangle $K-k-1, K, K-k$.

For points $q$ that are on a diagonal, take a sequence of points not on the diagonal whose limit us $q$. The finite union of closed central triangles is closed, and each of the points $p$ lie in a central triangle, hence so does $q$.

Why does this proof work for convex but not for non-convex? Where did we use convexity?

• That the pivot goes from vertices $1, k, 2k+1, k+1, \ldots$
• That the pivot going from vertices $1, k, 2k+1$ results in the beam intersection with the polygon giving us the desired central triangle
• That the point $p$ and corresponding line through vertex $K$ lies in central triangle $K - k, K , K + k$.

I do not know if the statement is true for non-convex polygons. I suspect it is not. This is not a counter example. It is just a diagram to stare at.