Geometry and the Discrete Fourier Transform

Continuing from: Geometry with the Discrete Fourier Transform

Interpolation with the Discrete Fourier Transform

The Steiner Ellipse

Any three non-coincident points in the plane have a unique ellipse passing through them such that the center of gravity of the ellipse is the same as the center of gravity of the initial three points. This ellipse is called Steiner's ellipse, and was studied in classical plane geometry.

With a classical mindset as to geometry one can readily see that there is such an ellipse: For three points at the vertices of an equilateral triangle there's clearly a circle passing through them that has the property that the center is the centroid of the circle and of the triangle. Any three distinct points are related by an affine transformation to the standard equilateral triangle configuration. The image under the affine transformation of the circle is the ellipse sought.

Here we'll an approach this construction using the discrete Fourier transform. Suppose one starts with three points $z_0, z_1, z_2\in \cplx$. The jump motion from point to point, $z_0$ to $z_1$ to $z_2$ to $z_0$, is what we want to interpolate with a motion $z(t)$ smoothly adjusting all three points to get to the next one. We shall assume, without essential loss of generality that the triangle $z_0,z_1,z_2$ is positively oriented so that the motion we construct will be too; otherwise we can just reverse the time parameter. We have the operator $J$ effecting the jump motion. What we need to get smoothly from $z_0$ to $z_1$ could then be just the curve $[0,1] \ni t \mapsto J^t z$. But this we can define neatly since we know how to diagonalize $J$. This means we can readily evolve $J$, writing \[ J^t = U\st (1\!:\!\omega^t\!:\!\omega^{2t})U = U\st (1\!:\!\omega^t\!:\!\bar\omega^{t})U. \]

Hence, if we write our interpolating curve as \[ [0,1]\ni t\mapsto z(t)=: (z_0(t),z_1(t),z_2(t)) \in \cplx^3. \] we have \[ z(t) = U\st (1\!:\!\omega^t\!:\!\bar\omega^{t})U z = U\st (1\!:\!\omega^t\!:\!\bar\omega^{t})U z= V\st (1\!:\!\omega^t\!:\!\omega^{-t}) f. \] In other words, to find the interpolating curve:

• Do the discrete Fourier transform.
• Leave the center of gravity alone.
• Evolve the two non-trivial coefficients rotationally in opposite directions with a rotation of ${2\pi t/3}$.
• Fourier transform back to get the new configuration.

If we consider $z(t)$ as evolving over the whole of $t\in[0,3]$ then we can note that \[ z_0(3)=z_1(2)=z_2(1)=z_0(0), \] and other such periodicities. We also see that the center of gravity of the complete curve has to be the original $f_0$, since the curve's points come in sets of 3 balanced about that point.

To verify that the curve is an ellipse it makes sense to do some preliminary simplification. Note that the transformations $t\mapsto z(t)$ are linear in $z$ for fixed $t$, so that we can transform the curve back to one whose center of gravity is the origin without changing its algebraic type. Therefore let us assume that $f_0=0$. Then we must look at \[z_0(t)=\tfrac13 (0+\omega^t f_1 + \omega^{-t}f_2). \]

Suppose, in polar coordinates $(\rho,\theta)$, that $f_1=\rho_1\ee^{\theta_1}$ and $f_2=\rho_2\ee^{\theta_2}$, and write $\omega=\ee^{\ii\varpi}$, i.e., $\varpi = 2\pi/3$. Then \begin{eqnarray*} z_0(t) &=& \rho_1\ee^{\ii (\varpi t + \theta_1)} + \rho_2\ee^{\ii (-\varpi t + \theta_2)}\\ &=&\ee^{\ii (\theta_1+\theta_2)/2}[\rho_1\ee^{\ii (\varpi t + (\theta_1-\theta_2)/2)} + \rho_2\ee^{-\ii (\varpi t +(\theta_1-\theta_2)/2)}]\\ &=&\ee^{\ii (\theta_1+\theta_2)/2} [(\rho_1+\rho_2)\cos(\varpi t + (\theta_1-\theta_2)/2)) + \ii(\rho_1-\rho_2)\sin(\varpi t +(\theta_1-\theta_2)/2)]. \end{eqnarray*} The first term in the last line is a pure rotation about the origin, which is the center of mass by assumption, and the second is the standard expression for a point on an ellipse with semi-major axis $(\rho_1+\rho_2)$ and semi-minor axis $(\rho_1-\rho_2)$. We have thus proved by explicit construction the existence of the Steiner ellipse for any three distinct points in the Euclidean plane, doing it by simple use of complex variables.

Conversely, given a non-degenerate ellipse in the plane we can find a triple of points whose Steiner ellipse it will be, but this the triple is not unique, of course. We can use these Fourier transform coordinates to give coordinates to the space of plane ellipses.

The easiest way to see this seems to be to consider a standard sort of ellipse. Any ellipse in the plane can be brought to have center at the origin by a simple translation that will only be reflected in the value of $f_0$. Any ellipse centered at the origin can be turned so that the semi-major axis lies along the $x$-axis; this rotation is only reflected in corresponding rotations of $f_1$ and $f_2$.

So let us assume a standard ellipse whose major axis extends from $-a$ to $a$, with $a$ real, and whose minor axis runs from $-b\ii$ to $b\ii$, with $b$ real; clearly, $a$ and $b$ may not be zero. The standard equation of our ellipse will thus be \[ \frac {x^2}{a^2} + \frac {y^2}{b^2} =1. \]

Consider the following three points: the right-hand end of the major axis, $a\in\cplx$, and the upper and lower ends of the chord of the ellipse perpendicular to the major axis at the point half way to the left from the center, $-\frac a2$, which are $\frac12(-a+\sqrt3 b\ii)$ and $\frac12(-a-\sqrt3 b\ii)$, respectively, as one may verify from the equation of the ellipse. From the triple \[ z = (a, \tfrac12(-a+\sqrt3 b\ii),\tfrac12(-a-\sqrt3 b\ii)) \] we form the discrete Fourier transform \[ f=\tfrac13 (0,a + \omega^2(\tfrac12(-a+\sqrt3 b\ii)+\omega\tfrac12(-a-\sqrt3 b\ii), a + \omega(\tfrac12(-a+\sqrt3 b\ii)+\omega^2\tfrac12(-a-\sqrt3 b\ii)). \] Consider the term \begin{eqnarray*} f_1 &=& \tfrac13[a + \omega^2(\tfrac12(-a+\sqrt3 b\ii))+\omega(\tfrac12(-a-\sqrt3 b\ii))]\\ &=&\tfrac13[ \tfrac{3}2a + \ii \tfrac{\sqrt3} 2 b (\omega^2-\omega)]\\ &=&\tfrac13 [\tfrac{3}2a - \ii \tfrac{\sqrt3} 2 b (2\omega+1)]\\ &=& \tfrac12[a+b] \end{eqnarray*} since $(2\omega+1)^2=4\omega^2+4\omega+1=-3$. Similarly, since only a change of sign of the $b$ term results from a switch of the powers of $\omega$, \[ f_2=\tfrac12(a-b). \] So the semi-major axis is $a=f_1+f_2$, and the semi-minor axis is $b=f_1-f_2$.

A rotation of the axis of the ellipse by $\ee^{\ii \theta}$ would result in a similar rotation of $f_1$ with respect to $f_2$. In fact $f_1$ would be displaced positively to $\ee^{\ii \theta/2}f_1$ and $f_2$ negatively to $\ee^{-\ii \theta/2}f_2$.

If we consider the standard ellipse as sitting within a standard circle of radius $a$ and the same center, then we see that the three points we started with are the intersections of the lines through the three cube roots of unity with the ellipse.

If we consider rotating the three cubic root lines by $\ee^{\ii \psi}$, say, and taking the intersections with the ellipse as the starting points to reckon the Steiner evolution, then we are in fact back at the situation analyzed above.

Note that the discrete Fourier transform, which does map triples of points to other triples, is far from volume-preserving on the triangles the points subtend. It happily maps completely non-degenerate triangles to linear ones.

Finally remark that, with hindsight, we might have guessed the Fourier transform form of the ellipse fairly directly. The parametric expression for a point on the standard ellipse is $z(t) = a \cos t + \ii b \sin t$. Expanding this we have $z(t) = \sfrac12 [a (\ee^{\ii t} + \ee^{-\ii t}) + \ii b (-\ii) (\ee^{\ii t} - \ee^{-\ii t}) ]= (a+b)\ee^{\ii t} + (a-b)\ee^{-\ii t}$, which is supposed to be the evolution path of the point $z(0)$. So it looks as though we might have been able to read off that $f_1 = a+b$ and $f_2 = a-b$, since each is, respectively, what gets multiplied by $\ee^{\ii t}$ and $\ee^{-\ii t}$.

More points than 3; higher cyclic groups

One can carry through most of the constructions given above in the case of three points in the plane for any number $N$ of points, but the special properties of ellipses do not have clear generalizations at the moment. What does remain true is that there is a natural global interpolating curve that passes through a list of $N$ given points in the plane, that it is smooth, and that it has the same center of gravity as the original cluster of points. The adjective global is suggestive of the fact that there is a clear sense in which the position of every initial point has generally an effect on the form of the curve as it passes between any two of the given points. A subtlety does arise, however, depending on the divisibility properties of $N$.

So consider a list of $N$ points in $\cplx$, $z=(z_0,\dots,z_{N-1})=(z_n, n\in0..N-1)\in \cplx^N$. Here we shall use the list notation $(x_n, n\in B)$ to mean a list of objects $x_n$ indexed by values of $n$ lying in an ordered set $B$; of course, this is just a notation for a particular function $x$ on the domain $B$. We shall think of the lists as row vectors when the separator is a comma. Similarly then $(x_n; n\in B)$ will mean a vertical or column list, and $(x_n\colon n\in B)$ a list running down the usual diagonal descending to the right. The discrete interval notation $i..j$ denotes the range of integers running from $i$ to $j$, inclusive of the end values.

Again consider $z\in L^2(\ints_{/N},m)$ with constant weights $m(n)=N^{-1}$. The inner product in this Hilbert space is again \[ \langle u,v\rangle := \sum_{g\in\ints_{/N}}\bar u(g) v(g) m(g) = \tfrac1N(\bar u_0 v_0 + \bar u_1 v_1 +\dots+ \bar u_{N-1} v_{N-1}). \]

Let $\omega=\omega_N=\ee^{\ii 2\pi /N}$ be $N$th root of unity in the upper half-plane with the smallest argument. We have $\omega^N=1$ and \[ 1+\omega+\omega^2+\dots+\omega^{N-1}= \sum(\omega^k, k\in0..N-1)=0, \] where summing over a finite list means adding all the elements together, with the understanding that an empty sum is $0$. Similarly a product $\prod$ over a finite list will mean complete multiplication, but an empty product gives 1.

The additive character list of the abelian cyclic group $\ints_{/N}$ is $(\chi_n, n\in 0..N-1)$ where \[ \chi_n = (\omega_N^{nk}, k\in0..N-1). \] Proceeding as before, we consider the inner products for $j,k\in0..N-1$ \begin{eqnarray*} \langle{\chi_j}|{\chi_k}\rangle &=& N\inv\sum (\bar\omega^{jl}\omega^{kl}, l \in 0..N-1)\\ &=&N\inv\sum (\omega^{(N-j+k)l}, l \in 0..N-1)\\ &=& [\![{j=k}[\!] \end{eqnarray*} where the logical characteristic function $[\![{j=k}[\!]$ is 1 if $j=k$ and 0 if $j\ne k$. This is because each character of a finite cyclic group corresponds to a one-dimensional representation and so is absolutely irreducible [M. Hall, {\it Theory of Groups}, Macmillan, New York, 1959, p. 271].

As before then we may decompose any list of points $z$, which subtend an $N$-gon, into harmonic components according to the characters and form a discrete Fourier transform \[ \cplx^N\ni (z_n, n\in0..N-1)=z \mapsto f = (\langle{\chi_n}|{z}\rangle,n\in0..N-1)\in \cplx^N, \] implemented by a multiple of the Vandermonde matrix \[ V=(\chi_n;n\in 0..N-1) = (\omega_N^{jk},j\in0..N-1;k\in0..N-1), \] \[ f=N\inv V z. \] We then can have an interpolating curve obtained as before \[ z(t) = V\st(\omega_N^{kt}:k\in0..N-1)f. \] The center of gravity remains fixed for the same reason as previously. We shall call the interpolating curve the Steiner interpolant of the $N$ initial points.

We remark that the curve \[ \reals\supset [0,N]\ni t \mapsto z_0(t) \in \cplx \] is plainly a closed smooth curve passing through through all the points of $(z_n, n\in0..N-1)$. Smoothness is clear since all the dependence on $t$ is built up from powers like $\omega_N^{kt}$, each of which is infinitely differentiable with respect to $t$.

Before discussing general properties of the Steiner interpolant, such as conditions of uniqueness, let us examine some other cases of small $N$.

$N=2$

The two-element additive group $\ints_{/2} = \{0,1\}$ has only one nontrivial character, namely the alternating character: \[ \chi_0 = (1,1)\quad;\quad \chi_1=(1,-1), \] so the Fourier transform of $(a,b)$ is $\sfrac12(a+b,a-b)$. The evolution on the interpolant is mediated by the power $(-1)^t=\ee^{\ii \pi t}$. Note that we start the simplest example with the center of gravity at 0, so we should be considering the symmetric case $(a,b)=(-c,c)$ for some $c\in\cplx$. The Fourier transform is $(0,\sfrac12(-2c)) = (0,-c)$. Then the Steiner interpolant will be the curve \[ [0,2]\ni t \mapsto \ee^{\ii \pi t}(-c) \in \cplx, \] which is a circle that runs through $-c$ and $c$. In this case there does not seem much more simple to say, except to note that a fundamental construction of elementary geometry is to run a circle through some point, or across some diameter, which is what's happening when you choose a center and a particular point on the circle.

$N=4$

The four-element additive group $\ints_{/4}= \{0,1,2,3\}$ has four additive characters: \[ \chi_0 = (1,1,1,1)\quad;\quad \chi_1=(1,\ii,-1,-\ii),\quad;\quad \chi_1=(1,-1,1,-1),\quad;\quad \chi_3=(1,-\ii,-1,\ii). \] The standard centered example is a quadrilateral $(a,b,c,d)$ with $a+b+c+d=0$. Then correspondingly \[ f_1=\tfrac14[(a-c)-\ii(b-d)]\quad,\quad f_2=\tfrac14[(a-b)+(c-d)]\quad,\quad f_3=\tfrac14[(a-c)+\ii(b-d)], \] so

or, if we write for brevity $C=\cos(\sfrac12 \pi t)$ and $S=\sin(\sfrac12 \pi t)$,

Continued by:

Polynomials and other relationships