13
$\begingroup$

I have the following elementary problem/question that I do not know how to tackle. It comes with a "math-olympiad-flavor" but I suspect it may be much more difficult than an high-school olympiads problem.

Let $\mathscr{P}$ be a simple polygon (not necessarily convex) in the plane, and such that the number of sides of $\mathscr{P}$ is an odd number $2k+1$.

For each vertex $v$ of $P$ there is an intuitive notion of opposite side (because the number of sides is odd), just label the sides counterclockwise at $v$ from $1$ to $2k+1$, and it would be the one with the label $k+1$.

Now suppose that for each vertex and its corresponding opposite side I consider the triangle the determine in the plane. Let us call $\Delta_v$ this triangle and call it a central triangle.

Is the following:

$$ \mathscr{P} \subseteq \bigcup_{v\in \mathscr{P}} \Delta_v$$

always true? In other words, if one paints all central triangles is it true that the whole polygon is then painted?

$\endgroup$
5
$\begingroup$

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):

                            5-pointed star

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.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The five-pointed star counterexample has me a bit confused, because the star evidently has an even number of sides. The question specified polygons having an odd number of sides... Was the star brought up only to consider the role of winding number? In any case, wouldn't having an even number of sides automatically defeat it being used at all? $\endgroup$ – Dr. Michael W. Ecker Nov 18 at 5:01
  • $\begingroup$ We're only thinking of the five "outer" corners as vertices here, with 5 sides - i.e., the star polygon {5/2}. $\endgroup$ – RavenclawPrefect Nov 18 at 6:01
  • 1
    $\begingroup$ OK. So the other five intersection points are not considered vertices, I infer. Well: a) Not knowing about (5, 2) and all that stuff, how would one know this is not a decagon? From calling it a five-point star? b) Is it just a coincidence that this picture could be construed as a non-convex decagon that has an even number of sides and therefore would not be considered for this theorem anyway? $\endgroup$ – Dr. Michael W. Ecker Nov 19 at 17:48
  • $\begingroup$ The five "inner" sides would give away that it's not just a decagon, at least, but I agree that in general the set of points spanned by the edges of a (possibly self-intersecting) polygon do not determine the polygon. We can define a polygon by a cyclic ordering of some points in the plane - there's a mapping from such cyclic orders to subsets of the plane by taking the union of line segments between adjacent vertices, but that isn't an injective function. In this problem the extra data of which vertices are where, and in which order, matters - it determines which triangles we draw. $\endgroup$ – RavenclawPrefect Nov 19 at 21:14
  • $\begingroup$ As to (b), it is basically a coincidence - imagine lowering the top vertex of the star until it sinks below the horizontal edge. The resulting self-intersecting pentagon will still not cover all of its interior (in particular, it omits the central kite shape), but the 7-gon you get from taking the exterior edges and vertices does cover all of its interior with triangles. $\endgroup$ – RavenclawPrefect Nov 19 at 21:16
2
$\begingroup$

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.

enter image description here


| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm not sure I see this. What points near $\overline{P_1P_2}$ are not filled in that are still in the non-convex polygon? $\endgroup$ – Brian Tung Nov 12 at 1:28
  • 1
    $\begingroup$ Triangles $\triangle P_1P_4P_5$ and $\triangle P_6P_2P_3$ seem to take care of all points near $\overline{P_1P_2}$. Or did I misunderstand the problem? $\endgroup$ – Brian Tung Nov 12 at 1:32
  • $\begingroup$ Your proof might just need to take care of points that are directly between two "nearly opposite" vertices. I don't think you need convexity, maybe? $\endgroup$ – Brian Tung Nov 12 at 1:39
  • $\begingroup$ @BrianTung Hm, yea that's doesn't quite work, moved down. I used convexity in the first claim, taking the intersection of the beam and the polygon. IE I want triangle 1-4-5, whereas the beam pivoted at 1 will include points on the other side of 4-5. $\endgroup$ – Calvin Lin Nov 12 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.