# Midpoint Polygon Conjecture

Standard

This is going to be yet another ambitious post like New Diagonal Contribution Theorem, and Cross Diagonal Cover Problem.

Let’s begin with following definitions from Wikipedia:

A convex polygon is a simple polygon (not self-intersecting) in which no line segment between two points on the boundary ever goes outside the polygon.

A concave polygon is a simple polygon (not self-intersecting) which has at least one reflex interior angle – that is, an angle with a measure that is between 180 degrees and 360 degrees exclusive.

We know that 3 sided polygons (a.k.a triangles) are always convex.  So, they are not very interesting. Let’s define the following procedure:

Midpoint Polygon Procedure: Given a n-sided simple polygon, join the consecutive midpoints of the sides to generate another n-sided simple polygon.

Here are few examples:

Red polygon is the original polygon, green polygon is the one generated by joining midpoints.

We observe that if the original polygon was a concave polygon then the polygon generated by joining midpoints need not be a convex polygon. So, let’s try to observe what happens when we apply the midpoint polygon procedure iteratively on the 4th case above (i.e. when we didn’t get a convex polygon):

In fourth iteration of the described procedure, we get the convex polygon.

Based on this observation, I want to make following conjecture:

Midpoint Polygon Conjecture: For every simple polygon there exists a smallest natural number $k$ such that after $k$ iterations of midpoint polygon procedure, we obtain a convex polygon.

If the given polygon is convex, then there is nothing to prove since $k=1$, but I have no idea about how to prove it for concave polygons. I tried to Google for the answer, but couldn’t find anything similar. So, if you know the proof or counterexample of this conjecture, please let me know.

### 10 responses »

1. Hi from https://www.reddit.com/r/mathpuzzles/
This is a cute problem.
We can identify a point with a complex number, and an n-gon (vertices labelled 1 through n) as a vector in $\mathbb{C}^n$.
Fix n.
The function M taking an n-gon to its midpoint polygon is a linear operator, so we can attempt an eigen-decomposition to understand it.
We can build M from a simpler operator which cycles the vertices — $M=(1+C)/2$, $C(v_1,\ldots,v_n)=(v_2,\ldots,v_n,v_1)$.
Eigenvectors of C are easy to find: fix a complex nth root of 1, $\omega = \cos(2\pi/n) + i \sin(2\pi/n)$, and for each k we have
$C P_k = \omega^k P_k$ for $P_k = (\omega^{1k}, \ldots, \omega^{nk})$.
These correspond to regular polygons or star-polygons, with vertices on the unit circle spaced $k/n$ of a full turn apart.
$P_0$ is a degenerate n-gon with all vertices at 1+0i. $P_1$ is a regular n-gon with vertices going counterclockwise. $P_1$ is the same, clockwise.
Others are star polygons, e.g. $P_2$ is a pentagram when $n=5$.
So M has the same eigenvectors: $M P_k = (1+\omega^k)/2 \cdot P_k$.
Let’s jump to n=5 (as things work all too nicely with just 3 or 4 sides).
An arbitrary 5 vertices can be represented as $a_0 P_0 + a_{-1} P_{-1} + a_1 P_1 + a_{-2} P_{-2} + a_2 P_2$.
On principle, we can drop the $P_0$ term (same as translating the polygon) and scale the rest (dilation/rotation).
We can restrict ourselves further and look at polygons of the form $P_1 + P_{-1} + c (P_2 - P_{-2})$, c real.
Long story short, Elwyn Berlekamp and coauthors got to this point decades ahead of me, found counterexamples (!), and wrote it up nicely in a short paper: https://dx.doi.org/10.2307%2F2313689.
However, a “generic” polygon won’t be a counterexample — if you picked vertices at random, your probability of hitting a counterexample would be zero.
The paper ties this to the ellipse idea in the other comment: your polygon tends toward an ellipse, which normally forces it to go convex after enough iterations, but not if the limiting ellipse is degenerate!

Liked by 2 people

• Thanks for making me happy! I hope that someday I am able to meet you and discuss lots of mathematics with you. You are a wonderful person.

I will be grateful if you could please tell me the branch of mathematics to which such questions belong to (since it appears that you have deep understanding of such problems).

Also, thanks to M. Scroggs for sharing this problem on Reddit (and for the second time helping me to solve a problem).

[I edited the latex syntax of your solution, so that WordPress is able to render it properly, if I introduced a typo then please let me know]

Like

• Thanks for the kind words, and for editing my post. It looks a lot better now.

This is definitely a geometry question. 🙂 I didn’t really have a lot of deep knowledge about it, but I’m happy to share my thought process:

– I really like spectral theory (and functional calculus) methods, so I noticed the similarity to a linear recurrence problem and ran with this approach. Before long, I was satisfied that it was working.
– Next, I looked for known results, to see if the problem had a name and perhaps learn from someone else’s more elegant solution. The Wikipedia article on Midpoint Polygons had the “Polygon Problem” paper in its citations. That sounded promising, and turned out to be the same problem.

Hope that helps.

Liked by 1 person

• Incidentally, currently I am doing a course on Differential Geometry in which a glimpse of spectral theory and functional analysis was given. But taking help of complex numbers to solve a Euclidean geometry problem was something I couldn’t appreciate while preparing for olympiads. I guess this is the reason why I missed the connection (and that’s why mathematics is fascinating, just like nature).

I am amazed to know that Wikipedia has a page on midpoint polygons (I just made-up the term “midpoint polygons” in order to replace the longer title “Concave-Convex polygon problem”).

Thank you 🙂

Like

2. While searching for an answer to your question, I found some interesting results that I think indicates your conjecture is true!
One fascinating result is, “No matter how random the initial Polygon, the edges eventually “uncross” and in the limit, the vertices appear to arrange themselves around an ellipse that is tilted forty-five degrees from the coordinate axes.”
There is a problem though with the pentagram, but your hypothesis rules it out. But I am not sure if this issue won’t be there for some other polygon even with your hypothesis of it being non-intersecting.
https://geometrycourse.wordpress.com/2013/07/11/sequences-of-inscribed-polygons/
http://oa.upm.es/4442/1/INVE_MEM_2008_60553.pdf

Like