Inscribed polygons and the Fourier transform
by David Radcliffe
Draw a polygon in the plane. We can construct a new polygon by connecting the midpoints of the original polygon. I will call this the midpoint process. What happens if we repeat this process many times?
It is clear that the polygons are shrinking to a point. We can also observe that the polygons appear to be approaching a limiting shape. I will explain why this is the case, and I will show that (except in very special cases) the limiting shape is an affine regular polygon, i.e. a regular polygon to which a linear transformation has been applied. Since linear transformations carry circles to ellipses, it follows that the limiting shape can be inscribed in an ellipse.
We will use complex numbers to analyze this problem. Every point in the plane is represented by a unique complex number. Similarly, a polygon with n vertices can be represented by a sequence of n complex numbers.
The equation has n solutions in the complex plane. They are
If we connect these points with line segments then we produce a regular polygon. This picture shows the six complex solutions to .
We can form other polygons by connecting the vertices in different ways.
Let be a fixed integer. For each integer between 0 and , let be the following polygon.
is a regular polygon, and is the same polygon with the opposite orientation. The other polygons are star polygons, except when divides . If and are not coprime, then the polygon has repeated vertices. The following picture shows , and when .
The “polygon” is rather boring. It consists of the same vertex 1, repeated n times. But we will need as well!
The discrete Fourier transform
A sequence of complex numbers is transformed into a new sequence by the formula
This transformation is called the discrete Fourier transform (DFT). It is an essential tool in signal processing and image processing, and it has many other important applications. In signal processing, the Fourier coefficients represent amplitudes, and the indices are frequencies.
The DFT is an invertible transformation, and the inverse is defined by
Applying this to the polygon , we obtain
In other words, every n-gon can be expressed uniquely as a linear combination of the .
Putting it all together
You might well be wondering what this has to do with the original problem. The key idea is that the midpoint process is very easy to understand when it is applied to a regular polygon or a star polygon. Applying the midpoint process to yields a smaller copy of . Of course, is unchanged by this process and remains a single point. But note that and shrink relatively slowly, and the other shrink more rapidly. See the figure below.
After many iterations, the polygon will look like
because the other components will be negligible.
But we recall that and are regular n-gons (with opposite orientations), and multiplication by a fixed complex number is a linear transformation. Therefore,
is an affine regular polygon.
There is one special case that needs to be noted. If and are both zero, then the limiting shape will not be as described above. For example, if we start with a 5-pointed star, then each iteration will yield a smaller 5-pointed star. But this is an unstable equilibrium. If we perturb the star by moving a vertex by an arbitrarily small amount, then and will no longer be zero, and the limiting shape will be an affine regular polygon.