Midpoint polygons?

A midpoint polygon is formed by taking the midpoints of each side of a polygon, and making a new polygon out of those points. The end result is the midpoint polygon inscribed in the polygon you started off with.

Given an arbitrary polygon, is it always the midpoint polygon of some other polygon? And if so, is this other polygon unique? Is there a simple construction to find it? And also, are there any special cases of the original question which are easier to answer?

• Yes to both existence and uniqueness if the polygon has an odd number of vertices, no to both if even. Hint: Try constructing the polygon starting from one vertex. At each step the next vertex is given by a $180^\circ$ rotation about one of the original polygon's vertices, and after $n$ steps you want to return to your original point. Now the composition of $n$ such rotations is either a $180^\circ$ or $360^\circ$ rotation... – Rahul Jan 2 '17 at 17:37
• How is the vertex given by a 180 degree rotation? I'm confused. – mathtron999 Jan 2 '17 at 17:52
• The rotations are not about the same point to be composed like that... – Momo Jan 2 '17 at 17:55
• What? @Momo I don't understand what you're saying – mathtron999 Jan 2 '17 at 18:02
• @Momo Yes I was a bit sloppy there. The composition of $180^\circ$ rotations about $n$ points $p_1,\ldots,p_n$ is either a $180^\circ$ rotation about some point $q$, or a translation, depending on the odd/evenness of $n$. This is the same as the map $(a,b)\mapsto(a_n,b_n)$ in your updated answer, except from a geometric viewpoint rather than an analytic one. – Rahul Jan 2 '17 at 18:27

Note that the midpoints of a quadrilateral form a parallelogram. So if a quadrilateral is not parallelogram it cannot be the midpoint polygon of another quadrilateral.

EDIT:

Let the vertices of the polygon be of coordinates $(x_1,y_1)\ldots(x_n,y_n)$ Suppose that we start from $(a,b)$ and we incrementally construct the broken line $(a,b),(a_1,b_1)\ldots(a_n,b_n)$ having midpoints as the original polygon:

$x_1=\frac{a+a_1}{2}$, $y_1=\frac{b+b_1}{2}$ so

$a_1=-a+2x_1$, $b_1=-b+2y_1$

$a_2=-a_1+2x_2$, $b_2=-b_1+2y_2$

$\ldots$

$a_n=-a_{n-1}+2x_n$, $b_n=-b_{n-1}+2y_n$

To have a closed polygon one needs $a_n=a$ and $b_n=b$

So for $n$ odd you get an unique solution:

$a=x_1-x_2+x_3-\ldots+(-1)^{n+1}x_n$

$b=y_1-y_2+y_3-\ldots+(-1)^{n+1}y_n$

For $n$ even, the two linear systems are not of full rank (have either an infinity of zero solutions). You may check when each of the case happens with Rouche's theorem

So when $n$ is even, the system has solution iff:

$x_1-x_2+x_3-\ldots-x_n=0$

$y_1-y_2+y_3-\ldots-y_n=0$

In which case it has an infinity of solutions, starting with any point of the plane.

Of course depending on your unspecified requirements on the polygon (non-degenerate, non-self-intersect, convex), you might have to impose additional restrictions.

• I add that this is true in general for all even $n$: the midpoint polygon always has opposite sides parallel. – MJD Jan 2 '17 at 17:39
• @MJD Are you sure? I can easily construct a hexagon $ABCDEF$ whose midpoint polygon has two opposite sides not parallel, just by making sure $AC$ and $DF$ are not parallel. – Rahul Jan 2 '17 at 17:49
• I definitely meant something, but I'm not sure what. I'll try to figure it out. – MJD Jan 2 '17 at 17:55
• @Momo I need to prove the existence and uniqueness for all polygons though, not just quadrilaterlas. – mathtron999 Jan 2 '17 at 18:05
• OK, i will add more – Momo Jan 2 '17 at 18:07

The midpoint transformation can be written in matrix form $Q=AP$, where $Q$ are the new vertices, $P$ are the old vertices, and the matrix $A$ is a circulant matrix whose first row is $1/2,1/2,0,\dots,0$.

The relevant property is that the rank of $A$ is $n-d$, where $d$ is the degree of $\gcd( x^{n-1}+1, x^n - 1)$. When $n$ is even, this gcd has at least the factor $x+1$ and so $A$ is singular and the midpoint transformation cannot be inverted.

The gcd is actually a divisor of $x+1= x(x^{n-1}+1)-(x^n - 1)$ and so is either $1$ or $x+1$. Therefore, $A$ is singular iff $n$ is even.

For brevity, let's say that if $X_1X_2X_3...X_n$ is a polygon, and $Y_1Y_2Y_3...Y_n$ its midpoint polygon, we will call $Y_1\dots Y_n$ the dual of $X_1\dots X_n$, and $X_1 \dots X_n$ a predual of $Y_1\dots Y_n$. The following results completely characterize when a polygon $Y_1 \dots Y_n$ has a predual, when that predual is unique, and when two different (i.e. noncongruent) polygons have the same (i.e. congruent) duals.

If $n$ is odd, then any polygon $Y_1 \dots Y_n$ has a unique predual.

If $n$ is even, things are much more complicated. Let $\vec{e_1}, \vec{e_2}, \dots \vec{e_n}$ denote the vectors that point from each vertex to the next; that is, $\vec{e_1} = \vec{Y_1Y_2},\vec{e_2}=\vec{Y_2Y_3},\dots \vec{e_n}=\vec{Y_nY_1}$. Then for any polygon it is certainly true that $\vec{e_1}+\vec{e_2}+\cdots+\vec{e_n}=0$. The following condition is necessary and sufficient to ensure that the polygon has a predual: we require that $\vec{e_1}+\vec{e_3}+\cdots+\vec{e_{n-1}}=0$ and $\vec{e_2}+\vec{e_4}+\cdots+\vec{e_{n}}=0$. In other words, the odd-numbered edges and the even-numbered edges separately add together to form two polygons.

In the case $n=4$, the condition above reduces to the requirement that $\vec{e_1}=-\vec{e_3}$ and $\vec{e_2}=-\vec{e_4}$, i.e., that the quadrilateral is a parallelogram.

Regarding uniqueness, form any two polygons $X_1X_3\dots X_{n-1}$ and $X_2X_4\dots X_n$ with an equal number of vertices. Let $X_2'X_4'\dots X_n'$ be any translation of $X_2X_4\dots X_n$ in the plane. Then the two polygons $X_1X_2X_3\dots X_{n-1}X_n$ and $X_1X_2'X_3\dots X_{n-1}X_n'$ have congruent duals.

Put another way: decompose any $2n$-gon into two $n$-gons by joining every other vertex. Then let those two $n$-gons "float" in the plane relative to one another. As they take different positions, the original $2n$-gon deforms into different shapes, but all of those different $2n$-gons have congruent duals. This is the only way that two different polygons can have the same dual.

Yes, we can!

(Besides for an even number of nodes, then the 'highest' frequency can not be retrieved.)

It can be done with a deconvolution in the Fourier domain:

$$P_0 = \mathcal{F}^{inv}\left(\frac{\mathcal{F}(P_1)}{\frac{1}{2} + \frac{1}{2}\exp(i\omega)}\right)$$

in which $P_0$ is the reconstructed polygon, $P_1$ is the midpoint polygon, $\mathcal{F}$ and $\mathcal{F}^{inv}$ are the forward and inverse Fourier transform.

Proof

I assume an $n$-dimensional polygon, but since for each dimension, the midpoint is calculated for each dimension separately, this reduces this problem to 1D.

The midpoint polygon $P_1$ of polygon $P_0$ is the running average thereof, with length 2. This boils down to a circular convolution with the filter $\{\frac{1}{2},\frac{1}{2}\}$.

According to the Convolution Theorem, we may retrieve $P_0$ from $P_1$ in the frequency domain, by dividing the spectrum of $P_1$ with the spectrum of the convolution filter $\{\frac{1}{2},\frac{1}{2}\}$, which is $\frac{1}{2} + \frac{1}{2}\exp(i\omega)$. This spectrum, has just one zero, at $\omega = \pi$ , the Nyquist frequency.

• Only for an even number of nodes, the Fourier Transformation 'samples' at the Nyquist frequency. And so, this cannot be retrieved with a deconvolution, as it was lost in the running average. Just consider the 1D example $\{1,0,1,0\}\rightarrow\{\frac12,\frac12,\frac12,\frac12\}$
• For an odd number of nodes, all values of the filter's spectrum are non-zero, and can thus be retrieved during deconvolution.

$\blacksquare$

PS: In practice, for an even number of nodes, the Nyquist frequency can best be set to zero, following Occam's razor, as this also minimizes the 'energy' of your polygon. Note that also other high frequencies are blown up, if the midpoint polygon was acquired from a noisy measurement. These could therefore be either set to zero, or you can use another type of regularization, if additional information about the initial polygon is available. For example, if you know that the number of turns is relatively sparse, you can use $\ell_1$ regularization.