Convolution filters for polygons and the Petr–Douglas–Neumann theorem

Abstract

We use the discrete Fourier transformation of planar polygons, convolution filters, and a shape function to give a very simple and enlightening description of circulant polygon transformations and their iterates. We consider in particular Napoleon’s and the Petr–Douglas–Neumann theorem.

1 Introduction

If $\Delta$ is a positively oriented equilateral triangle and if one erects right-hand isosceles ears with base angles $\frac{\pi }{6}$ on the sides of $\Delta$, the ears’ apices are the vertices of a positively oriented equilateral triangle (Fig. 1); if $\Delta$ is a negatively oriented equilateral triangle, the apices of these right-hand ears coincide with the centroid of $\Delta$. Admit for the moment that each nonequilateral and nontrivial triangle $\Delta _1$ is the sum of a positively and of a negatively oriented equilateral triangle, and admit also that ears’ erection commutes with triangles’ addition: Napoleon’s theorem is proven! Indeed, if one erects three right- or three left-hand ears with base angles $\frac{\pi }{6}$ on the sides of (each term of the sum decomposition of ) $\Delta _1$, the (global) ears’ apices always form an equilateral triangle.

Fig. 1

Napoleon’s theorem for equilateral triangles

The apices of ears erected on the sides of a planar $n$-gon $\Pi$ can be obtained by convolving the given polygon with an appropriate polygon $\Gamma$ (see Sect. 3). The convolution with $\Gamma$ acts as a filter on $\Pi$ since the spectrum of the convolution product $\Pi *\Gamma$ in the Fourier base of $\mathbf C ^n$ is given by the entrywise product of the spectra of $\Pi$ and $\Gamma$ (see Sects. 2 and 3). It is thus possible to filter targeted frequencies one by one out of $\Pi$ by consecutive convolutions with suitable polygons and to get for example Napoleon’s theorem or the Petr–Douglas–Neumann theorem (Petr 1905; Douglas 1940; Neumann 1941, 1942; Baker 1942; Chang and Davis 1983; Martini 1996; Pech 2001). The Fourier decomposition of a polygon and circulant matrices have been used for a long time for studying polygon transformations with a circulant structure (Darboux 1878; Schoenberg 1950; Berlekamp et al. 1965; Shapiro 1984; Fisher et al. 1985; Grünbaum 1999; Vartziotis and Wipper 2009, and some of the previous references). We feel nevertheless that the true nature of such polygon transformations cannot be understood without our convolution filter approach, which is remarkably simple and completely free from matrix algebra. The method presented here has already been very successful for analyzing triangle transformations (Nicollier and Stadler 2013; Nicollier 2013): we generalize in particular the powerful notion of shape of triangles by defining the shape of an arbitrary planar polygon as the homogeneous coordinates given by the spectrum of this polygon without offset. See Lester (1996a); Lester (1996b); Lester (1997) for another shape of triangles.

2 Fourier transform of a planar polygon

Consider an $n$-gon $\Pi$ of the complex plane, $n\ge 2$, as a point $\Pi =(z_k)_{k=0}^{n-1}\in \mathbf C ^n$ representing the closed polygonal line $z_0\rightarrow z_1\rightarrow \dots \rightarrow z_{n-1}\rightarrow z_0$ starting at $z_0$: there are up to $n!$ $n$-gons with the same vertices. A polygon is called trivial when it is reduced to an $n$-fold point.

Endow $\mathbf C ^n$ with the inner product

$$\begin{aligned} \left<\Pi ,\Pi _1\right>=\left<(z_k)_{k=0}^{n-1},(w_k)_{k=0}^{n-1}\right>=\frac{1}{n}\sum _{k=0}^{n-1}z_k\overline{w_k} \end{aligned}$$

and set $\zeta =e^{i2\pi /n}$. The regular $\{n/k\}$-gons

$$\begin{aligned} f_k=\left( \zeta ^{k\ell }\right) _{\ell =0}^{n-1},\quad k=0,1,\dots ,n-1, \end{aligned}$$

form the orthonormal Fourier base of $\mathbf C ^n$ (Fig. 2): $f_ 0=(1,1,\dots ,1)$ is a trivial polygon, the other base polygons are centered at the origin, and the number of different vertices of $f_k$ is $n/\gcd (n,k)$. The discrete Fourier transform or spectrum of $\Pi$ is the polygon $\widehat{\Pi }=(\hat{z}_k)_{k=0}^{n-1}$ given by the spectral representation of $\Pi$ in the Fourier base:

$$\begin{aligned} \Pi =\sum _{k=0}^{n-1}\hat{z}_kf_k\quad \text{ with }\quad \hat{z}_k=\left<\Pi ,f_k\right>,\quad k=0,1,\ldots ,n-1, \end{aligned}$$

where each nonzero $\hat{z}_k$ rotates and scales up or down the base polygon about the origin. The color $\Pi$ is just a mix of complex quantities of the fundamental colors $f_1, f_2, \ldots , f_{n-1}$ around the colorless trivial polygon $\hat{z}_0f_0$, the offset, corresponding to the centroid $\hat{z}_0$ of $\Pi$. Note that a polygon has the form $af_k+bf_{n-k}=af_k+b\overline{f_k}$ with $a,b\in \mathbf C$ and $k\in \{1,\dots ,n-1\}$ exactly when it is the image of $f_k$ under some linear transformation of the cartesian plane (Schoenberg 1950): this transformation is unique if $(a,b)\ne (0,0)$ and $k\ne \frac{n}{2}$ (this corrects a small error of Schoenberg).

Fig. 2

Fourier base of $\mathbf C ^8$

The shape $\sigma _{\Pi }=\sigma (z_0,\dots ,z_{n-1})$ of the polygon $\Pi =(z_k)_{k=0}^{n-1}$ of $\mathbf C ^n$ is the point of the augmented complex projective space $\mathbf CP ^{\,n-2}\cup \{0\}$ with homogeneous coordinates $[\hat{z}_1:\cdots :\hat{z}_{n-1}]$. The polygons $\Pi$ and $\Pi _1$ are thus equally shaped if and only if $\Pi _1=a\Pi +bf_0$ for some $a,b\in \mathbf C$, $a\ne 0$. For $n=3$, the shape of a nontrivial triangle $(z_0,z_1,z_2)$ can be considered as the number $\hat{z}_2/\hat{z}_1$ of the extended complex plane (Nicollier 2013 and, without any reference to Fourier transforms, Nakamura and Oguiso 2003; Hajja et al. 2006).

The set $\mathrm{supp}_{\widehat{\Pi }}=\{k\mid \hat{z}_k\ne 0\}$ formed by the subscripts of the Fourier base polygons with a nonzero contribution to $\Pi$ is called support of $\widehat{\Pi }$. The shape’s support is $\mathrm{supp}_{\sigma _{\Pi }}=\mathrm{supp}_{\widehat{\Pi }}{\setminus }\{0\}$.

Suppose that we start from the polygon $\Pi$ and successively filter out one fundamental color after the other in any order, and this $n-2$ times: if the remaining fundamental color $f_{k_0}$ appears in $\Pi$, the filtered $\Pi$ is monochromatic with the color and the shape of $f_{k_0}$; otherwise, the filtered $\Pi$ is trivial. This is the Petr–Douglas–Neumann theorem (once the corresponding filters have been described).

3 Convolution filters

We consider a filter $T_{\Gamma }:\mathbf C ^n\rightarrow \mathbf C ^n$ given by the cyclic convolution $*$ with a fixed polygon $\Gamma =(c_0,c_1,\dots ,c_{n-1})$: the $k$th entry of $\Pi *\Gamma =\Gamma *\Pi$ is

$$\begin{aligned} \sum _{\ell _1+\ell _2=k\!\!\!\!\! \pmod {n}}z_{\ell _1}c_{\ell _2}=\sum _{\ell =0}^{n-1}z_\ell c_{{k-\ell \!\!\!\!\! \pmod {n}}},\quad k=0,1,\dots ,n-1. \end{aligned}$$

A circulant linear transformation of a polygon in the complex plane that is given by the coefficients $(a_k)_{k=0}^{n-1}$ of the circulant linear combination of the vertices is simply the convolution of the initial polygon with the polygon $(a_0,a_{n-1},a_{n-2},\dots ,a_1)$ obtained from $(a_0,a_1,\dots ,a_{n-1})$ by going the other way around. The operator $*$ is commutative, associative and bilinear.

Since $f_k*f_{\ell }={\left\{ \begin{array}{ll}nf_k&{}(k=\ell )\\ (0,0,\dots ,0)&{}(k\ne \ell )\end{array}\right. }$,   one has

$$\begin{aligned} T_{\Gamma }(\Pi )=\Pi *\Gamma =\left( \;\sum _{k=0}^{n-1} \hat{z}_kf_k\right) *\left( \;\sum _{\ell =0}^{n-1}\hat{c}_{\ell }f_{\ell } \right) =\sum _{k=0}^{n-1}n\hat{c}_k\hat{z}_kf_k, \end{aligned}$$

i.e., $\widehat{\Pi *\Gamma }=n\widehat{\Pi }\cdot \widehat{\Gamma }$, where $\cdot$ is the entrywise product: the Fourier base is a base of eigenvectors of the convolution $T_{\Gamma }$ with eigenvalues $n\hat{c}_k$. For $k\ge 1$, these eigenvalues are the homogeneous coordinates of $\sigma _\Pi$. The shape of a convolution product is given by the entrywise product of the homogeneous coordinates of the shapes, and the support of the resulting shape is the intersection of the supports of the individual shapes. A fundamental color survives to a (multiple) convolution if and only if it is present in every involved polygon: a convolution product of polygons is thus trivial if and only if the supports of their shapes have an empty intersection.

The cyclic left shift $\Pi =(z_k)_{k=0}^{n-1}\mapsto (z_1,\dots ,z_{n-1},z_0)$ is given by the convolution $\Pi *(0,\dots ,0,1)=\sum _{k=0}^{n-1}\zeta ^k\hat{z}_kf_k$. A direction reversing $\Pi \mapsto (z_0,z_{n-1},\dots ,z_1)$ implies the same reversing for the spectrum and for the shape: $(z_0,z_{n-1},\dots ,z_1)=\hat{z}_0f_0+\sum _{k=1}^{n-1}\hat{z}_{n-k}f_k$. Using for example $\widehat{\widehat{\Pi }}=\frac{1}{n}(z_0,z_{n-1},\dots ,z_1)$, one obtains easily that the vertices of $\Pi$ are collinear if and only if $\sigma _\Pi =[w_1:\cdots :w_{n-1}]$ with $w_{n-k}=\overline{w_{k}}$ for all $k\in \{1,\dots ,n-1\}$.

$T_{\Gamma }(\Pi )$ and $\Pi$ always have the same centroid if and only if $\sum _{k=0}^{n-1}c_k=1$, which means $\hat{c}_0=\frac{1}{n}$; the centroid is always translated to the origin if and only if $\hat{c}_0=0$. The convolution filter $T_{\Gamma }$ is bijective if and only if the support of $\widehat{\Gamma }$ is maximal, and the inverse filter is then the convolution with $\sum _{k=0}^{n-1}\frac{1}{n^2\hat{c}_k}f_k$.

The image by $T_{\Gamma }$ of the Dirac polygon $(1,0,\dots ,0)=\frac{1}{n}\sum _{k=0}^{n-1}f_k$ is $\Gamma$, the impulse response of the filter $T_{\Gamma }$, and the filter output is the convolution of the input with the impulse response, as for every linear time-invariant filter; the convolution with the Dirac polygon is the identity.

One has $T_{\Gamma _1}\circ T_{\Gamma _2}=T_{\Gamma _2}\circ T_{\Gamma _1}=T_{\Gamma _1*\Gamma _2}$. The iterates of $T_{\Gamma }$ are the convolution filters $T_{\Gamma }^m:\Pi =(z_k)_{k=0}^{n-1}\mapsto \sum _{k=0}^{n-1}(n\hat{c}_k)^m\hat{z}_kf_k$, $m\in \mathbf N$, with centroid $(n\hat{c}_0)^m\hat{z}_0$. The sum of the squared distances between the centroid and the vertices of $T_{\Gamma }^m(\Pi )$ is $n\sum _{k=1}^{n-1}(n|\hat{c}_k|)^{2m}|\hat{z}_k|^2$: the diameter of $T_{\Gamma }^m(\Pi )$ tends to $0$ for all $\Pi$ when $m\rightarrow \infty$ if and only if $|\hat{c}_k|<\frac{1}{n}$ for $k=1,\dots ,n-1$; this diameter remains bounded for every $\Pi$ exactly when $|\hat{c}_k|\le \frac{1}{n}$ for $k=1,\dots ,n-1$, and it tends to $\infty$ for all nontrivial $\Pi$ if and only if $|\hat{c}_k|>\frac{1}{n}$ for $k=1,\dots ,n-1$. The behavior of the shape of a polygon $\Pi$ under iterated convolution with $\Gamma$ is a matter of domination between the eigenvalues $n\hat{c}_\ell$, $\ell \in \mathrm{supp}_{\sigma _\Pi }$: $T_{\Gamma }^m(\Pi )$ is trivial for all $m\ge 1$ if and only if the support of $\widehat{\Pi *\Gamma }$, i.e., of $\widehat{\Pi }\cdot \widehat{\Gamma }$, is empty or $\{0\}$. If one sets $M=\max _{k\in \mathrm{supp}_{\sigma _{\Pi }}}|\hat{c}_k|$, $T_{\Gamma }^m(\Pi )-(n\hat{c} _0)^m\hat{z}_0f_0$ is otherwise asymptotically equal, at its scale, to

$$\begin{aligned} (nM)^m\sum _{k\in \mathrm{supp}_{\sigma _\Pi }\text{ with } |\hat{c}_k|=M} e^{im\arg \hat{c}_k}\hat{z}_k f_k \end{aligned}$$

(3.1)

when $m\rightarrow \infty$, and the shape of $T_{\Gamma }^m(\Pi )$ is asymptotically the shape of

$$\begin{aligned} \sum _{k\in \mathrm{supp}_{\sigma _\Pi }\text{ with } |\hat{c}_k|=M}e^{im \arg \hat{c}_k}\hat{z}_k f_k. \end{aligned}$$

(3.2)

The formulae (3.1) and (3.2) are equal for all $m\ge 1$ to $T_{\Gamma }^m(\Pi )-(n\hat{c}_0)^m\hat{z}_0f_0$ and to its shape if and only if $|\hat{c}_k|$ is constant for $k\in \mathrm{supp}_{\widehat{\Pi }\cdot \widehat{\Gamma }}{\setminus }\{0\}$; (3.1) and (3.2) are otherwise different from $T_{\Gamma }^m(\Pi )-(n\hat{c}_0)^m\hat{z}_0f_0$ and from its shape for all $m\ge 1$.

The shape of $T_{\Gamma }^m(\Pi )$ is periodic if and only if the following condition is satisfied: up to a common nonzero factor, all $\hat{c}_k$ with $k\in \mathrm{supp}_{\sigma _\Pi }$ lie on the unit circle with rational multiples of $\pi$ as arguments (see Nicollier (2013) for the triangle case $n=3$). If $|\hat{c}_1|$, $|\hat{c}_2|,\dots , |\hat{c}_{n-1}|$ are all different and nonzero, the filter $T_\Gamma$ is smoothing, i.e., $T_{\Gamma }^m(\Pi )$ converges in shape for every nontrivial $\Pi$ to the Fourier base polygon $f_\ell$ corresponding to the dominating $|\hat{c}_\ell |=\max _{k\in \mathrm{supp}_{\sigma _\Pi }}|\hat{c}_k|$.

4 The Petr–Douglas–Neumann theorem

A Kiepert $n$ -gon consists of the apices of similar triangular ears that are erected in order on the sides of the initial polygon $\Pi =(z_k)_{k=0}^{n-1}$ (beginning with the side $z_0\rightarrow z_1$) and that are directly similar to the normalized triangle $(0,1,u)\in \mathbf C ^3$ with apex $u$: the apex of the ear for the side $z_{0}\rightarrow z_1$ is defined as $z_1+u(z_0-z_1)$; it is a right-hand ear if $\mathrm Im u >0$. The corresponding Kiepert polygon is thus given by the centroid-preserving convolution of $\Pi$ with $K(u)=(u,0,\dots ,0,1-u)$ of spectrum

$$\begin{aligned} \frac{1}{n}\left( u+(1-u)\zeta ^k\right) _{k=0}^{n-1}=\frac{1}{n}\left( \zeta ^k+(1-\zeta ^k) u\right) _{k=0}^{n-1}. \end{aligned}$$

Note that $T_{K(0)}$ is the left shift. $K(u)$ is orthogonal to $f_\ell$, $\ell \ne 0$, exactly for $u=u_\ell =\frac{1}{1-\zeta ^{-\ell }}$. One has $u_\ell =\frac{1}{2}+\frac{i}{2}\tan \left( \ell \frac{\pi }{n}-\frac{\pi }{2}\right)$ since the isosceles ears on the sides of $f_\ell$ given by this value have indeed their apices at the origin (Fig. 2).

The Petr–Douglas–Neumann Theorem If one sets $\zeta =e^{i2\pi /n}$ and

$$\begin{aligned} u_\ell =\frac{1}{1-\zeta ^{-\ell }}=\frac{1}{2}+\frac{i}{2}\tan \left( \ell \frac{\pi }{n}-\frac{\pi }{2}\right) ,\;\ell \in \{1,2,\dots ,n-1\}, \end{aligned}$$

the convolution of an $n$ -gon $\Pi =(z_k)_{k=0}^{n-1}$ with

$$\begin{aligned} K(u_\ell )=(u_\ell ,0,\dots ,0,1-u_\ell )=(u_\ell ,0,\dots ,0,\overline{u_\ell }) \end{aligned}$$

adds isosceles ears with base angles $\ell \frac{\pi }{n}-\frac{\pi }{2}$ on the sides of $\Pi$ in order, beginning with the side $z_0\rightarrow z_1$ (the ears are left-hand when the base angles are negative). The support of $\widehat{K(u_\ell )}$ is $\{0,1,\dots ,n-1\}{\setminus }\{\ell \}$ and

$$\begin{aligned} K(u_\ell )&= \frac{1}{n}f_0+\frac{1}{n}\sum _{\genfrac{}{}{0.0pt}1{k=1}{k\ne \ell }}^{n-1}\frac{u_\ell }{u_{\ell -k\!\!\!\!\!\!\pmod {n}}}f_k=\frac{1}{n}f_0+\frac{1}{n}\sum _{k=1}^{n-1}\frac{\zeta ^{k}-\zeta ^{\ell }}{1-\zeta ^{\ell }}f_k\nonumber \\&= \frac{1}{n} f_0+\frac{1}{n\sin \left( \ell \frac{\pi }{n}\right) }\sum _{k=1}^{n-1}\sin \left( (\ell -k)\frac{\pi }{n}\right) e^{i k \pi /n}f_k. \end{aligned}$$

(4.1)

Proof

The second line of (4.1) follows from the inscribed angle theorem applied to the first line. The rest is already proven. $\square$

The spectrum of $\Pi *K(u_\ell )$ has the support $\mathrm{supp}_{\widehat{\Pi }}{\setminus }\{\ell \}$: the convolution of $\Pi$ with $K(u_\ell )$ erases the fundamental color $f_\ell$ from $\Pi$ (if not already absent) without deleting the nonzero contributions of the other Fourier base vectors. The polygon $\Pi *K(u_{\ell _1})*K(u_{\ell _2})*\cdots *K(u_{\ell _j})$ does not depend on the order of $\ell _1,\dots ,\ell _j$ and its spectrum has the support $\mathrm{supp}_{\widehat{\Pi }}{\setminus }\{\ell _1,\dots ,\ell _j\}$; $\Pi *K(u_1)*K(u_2)*\cdots *K(u_{n-1})$ is in particular reduced to the $n$-fold centroid of $\Pi$. By filtering the nontrivial $n$-gon $\Pi =(z_k)_{k=0}^{n-1}$ with the convolution product of all $K(u_\ell )$ but one, say but $K(u_{\ell _0})$, one obtains the polygon

$$\begin{aligned} \hat{z}_0f_0+\left( \prod _{\ell \in \{1,\dots ,n-1\}\setminus \{\ell _0\}} \frac{u_\ell }{u_{\ell -\ell _0 \!\!\!\!\!\!\pmod {n}}}\right) \hat{z}_{\ell _0}f_{\ell _0}, \end{aligned}$$

(4.2)

which is the centroid of $\Pi$ if $\Pi$ is orthogonal to $f_{\ell _0}$ and which is otherwise monochromatic with the shape of $f_{\ell _0}$. For $\ell _0=1$, this is the most widely known form of the Petr–Douglas–Neumann theorem. For $n=3$, this is Napoleon’s theorem in its right- or left-hand version according as $\ell _0=1$ or $2$, respectively. For $n=4$, van Aubel’s theorem follows graphically at once (Fig. 3) since it amounts to $\sum _{k=0}^3\hat{z}_k(f_k*K(u_3))$ and $\sum _{k=0}^3\hat{z}_k(f_k*K(u_3)*K(u_1))$: if right-hand squares are erected on the successive sides of a planar quadrilateral $\mathcal Q$ and if the vertices of $\mathcal Q _1$ are the midpoints of these squares in order, the left-hand squares constructed on the sides of $\mathcal Q _1$ have a common center or alternately equal centers. Moreover, the diagonals of $\mathcal Q _1$ are perpendicular and of equal length. Note that $\mathcal Q *K(u_2)$ is the midpoint quadrilateral: as linear combination of $f_0$, $f_1$, and $f_3$, it is an affine image of the square $f_1$, hence a parallelogram.

Fig. 3

Spectral representation of van Aubel’s theorem

The product in (4.2) can be computed explicitly. Since the factors are $\frac{\zeta ^{\ell _0}-\zeta ^{\ell }}{1-\zeta ^{\ell }}$, $\ell \in \{1,2,\dots ,n-1\}{\setminus }\{\ell _0\}$, the inscribed angle theorem shows that $\ell _0-1$ factors have the argument $\ell _0\frac{\pi }{n}-\pi$ and that the argument of the other $n-\ell _0-1$ factors is $\ell _0\frac{\pi }{n}$: the argument of the product is thus $\pi -\ell _0\frac{2\pi }{n}$; the modulus of the product is $1$ since every distance $|\zeta ^{\ell _0}-\zeta ^{\ell }|$ appears as modulus of some matching denominator. (4.2) becomes

$$\begin{aligned} \Pi *\left( \underset{\ell \ne \ell _0}{\Large *}K(u_\ell )\right) = \hat{z}_0f_0-\zeta ^{-\ell _0}\hat{z}_{\ell _0}f_{\ell _0}. \end{aligned}$$

$-\zeta ^{-\ell _0}\hat{z}_{\ell _0}f_{\ell _0}$ is the initial monochromatic component $\hat{z}_{\ell _0}f_{\ell _0}$ of $\Pi$ after a right shift of its vertices, i.e., a start from the last vertex $\hat{z}_{\ell _0}\zeta ^{-\ell _0}$ instead of $\hat{z}_{\ell _0}$, and after a half-turn about the origin; if $n$ is even, this corresponds to a start from the vertex $\hat{z}_{\ell _0}\zeta ^{-\ell _0+\frac{n}{2}}$. $\Pi$ and its spectrum can thus be recovered from the $n-1$ filtered polygons $\Pi *\left( \underset{\ell \ne \ell _0}{\Large *}K(u_\ell )\right)$, $\ell _0=1,\dots ,n-1$.