Towards Off-the-Grid Algorithms for Total Variation Regularized Inverse Problems

Abstract

We introduce an algorithm to solve linear inverse problems regularized with the total (gradient) variation in a gridless manner. Contrary to most existing methods, that produce an approximate solution which is piecewise constant on a fixed mesh, our approach exploits the structure of the solutions and consists in iteratively constructing a linear combination of indicator functions of simple polygons.

Appendices

A Derivation of Algorithm 2

See [19, Sec. 4.1] for the case of the sparse spikes problem.

Lemma 2

Problem ($\mathcal {P}_{\lambda }$) is equivalent to

with

and , i.e. if u is a solution of ($\mathcal {P}_{\lambda }$), then we have that ${(u,|\mathrm {D}u|(\mathbb {R}^2))}$ is a solution of ($\tilde{\mathcal {P}}_{\lambda }$), and conversely any solution of ($\tilde{\mathcal {P}}_{\lambda }$) is of the form $(u,|\mathrm {D}u|(\mathbb {R}^2))$ with u a solution of ($\mathcal {P}_{\lambda }$).

Proof

If $u^*$ is a solution of ($\mathcal {P}_{\lambda }$), then

$$\begin{aligned} T_{\lambda }(u^*)\le T_{\lambda }(0)=||y||^2/2\,. \end{aligned}$$

Hence, we have that $|\mathrm {D}u^*|(\mathbb {R}^2)\le M$, which shows the feasible set of ($\mathcal {P}_{\lambda }$) can be restricted to functions u which are such that ${|\mathrm {D}u|(\mathbb {R}^2)\le M}$. It is then straightforward to show that the resulting program is equivalent to ($\tilde{\mathcal {P}}_{\lambda }$), in the sense defined above. $\square$

The objective $\widetilde{T}_{\lambda }$ of ($\tilde{\mathcal {P}}_{\lambda }$) is now convex, differentiable and we have for all $(u,t)\in \mathrm {L}^2(\mathbb {R}^2)\times \mathbb {R}$

$$\begin{aligned} \begin{aligned} \mathrm{d}\tilde{T}_{\lambda }(u,t):\mathrm {L}^2(\mathbb {R}^2)\times \mathbb {R}&\rightarrow \mathbb {R} \\ (v,s)&\mapsto \left[ \int _{\mathbb {R}^2} \Phi ^*(\Phi u-y)\,v\right] +\lambda s\,. \end{aligned} \end{aligned}$$

Moreover, the feasible set C is weakly compact. We can therefore apply Frank–Wolfe algorithm to ($\tilde{\mathcal {P}}_{\lambda }$). The following result shows how the linear minimization step (Line 2 of Algorithm 1) one has to perform at step k amounts to solving the Cheeger problem (7) associated with .

Proposition 14

Let $(u,t)\in C$ and . We also denote

(26)

Then, if $\alpha \le 1$, (0, 0) is a minimizer of $d\tilde{T}_{\lambda }(u,t)$ over C. Otherwise, there exists a simple set E achieving the supremum in (26) such that, denoting $\epsilon =\text {sign}\left( \int _{E}\eta \right)$, $\left( \frac{\epsilon M}{P(E)}\mathbf {1}_E, M\right)$ is a minimizer of $d\tilde{T}_{\lambda }(u,t)$ on C.

Proof

The extreme points of C are (0, 0) and the elements of

$$\begin{aligned} \left\{ \left( \pm \frac{M}{P(E)}\mathbf {1}_E,M\right) ~\bigg |~E \text { is simple},~0<|E|<+\infty \right\} . \end{aligned}$$

Since $d\tilde{T}_\lambda (u,t)$ is linear, it reaches its minimum on C at least at one of these extreme points. We hence have that

$$\begin{aligned} (0,0)\in \underset{(v,s)\in C}{\text {Argmin}}~d\tilde{T}_{\lambda }(u,t)(v,s) \end{aligned}$$

or that a minimizer can be found by finding an element of

$$\begin{aligned} \begin{aligned}&\underset{\begin{array}{c} E\text { simple}\\ \epsilon \in \{-1,1\} \end{array}}{\text {Argmin}}~ \left\langle \Phi u-y, \frac{\epsilon M}{P(E)}\Phi \mathbf {1}_E\right\rangle +\lambda M\\ =&\underset{\begin{array}{c} E\text { simple}\\ \epsilon \in \{-1,1\} \end{array}}{\text {Argmin}}~ \left\langle \Phi u-y,\frac{\epsilon }{\lambda P(E)}\Phi \mathbf {1}_E\right\rangle \\ =&\underset{\begin{array}{c} E\text { simple}\\ \epsilon \in \{-1,1\} \end{array}}{\text {Argmin}}~ \frac{\epsilon }{P(E)} \int _E \frac{1}{\lambda }\Phi ^*\left( \Phi u-y\right) . \end{aligned} \end{aligned}$$

This last problem is equivalent to finding an element of

$$\begin{aligned} \underset{E\text {simple}}{\text {Argmax}}~~\frac{1}{P(E)}\left| \int _E \eta \right| , \end{aligned}$$

in the sense that $E^*$ is optimal for the latter if and only if the couple $\left( E^*,\text {sign}\left( \int _{E^*}\eta \right) \right)$ is optimal for the former. We can moreover show that (0, 0) is optimal if and only if for all ${E\subset \mathbb {R}^2}$ such that $0<|E|<+\infty$ and $P(E)<+\infty$ we have:

$$\begin{aligned} \frac{1}{P(E)}\left| \int _{E}\eta \right| \le 1\,. \end{aligned}$$

$\square$

B Discussion on Line 10 of Algorithms 2 and 3

Considering “Appendix A” and Algorithm 1, the standard Frank–Wolfe update at iteration k would be to take $u^{[k+1]}$ equal to ${\tilde{u}^{[k+1]}}$ with:

where ${\gamma _k=\frac{2}{k+2}}$, $E_*$ is the set obtained at Line 5 and $\epsilon _*$ is the sign of $\int _{E_*}\eta ^{[k]}$. Now, one can write $\tilde{u}^{[k+1]}$ as a linear combination of indicator functions of its level sets and then, apply the decomposition mentioned in Sect. 2.1 to each level set. This allows to find a family $(E_i)_{i=1}^N$ of simple sets of positive measure and $(a_i)_{i=1}^N\in \mathbb {R}^N$ such that ${\tilde{u}^{[k+1]}=\sum _{i=1}^N a_i\,\mathbf {1}_{E_i}}$ and

$$\begin{aligned} \left| \mathrm {D}\left( \sum \limits _{i=1}^N a_i\,\mathbf {1}_{E_i}\right) \right| (\mathbb {R}^2)=\sum \limits _{i=1}^N |a_i|\,P(E_i)\,. \end{aligned}$$

Moreover, it is possible to prove (see [20]) that for every $i\ne j$

• 1. Either $E_i\subset E_j$, $E_j\subset E_i$ or $E_i\cap E_j=\emptyset$.

• 2. If $\mathrm {sign}(a_i)=\mathrm {sign}(a_j)$ and $E_i\cap E_j=\emptyset$, then it holds that ${\mathcal {H}^1(\partial ^* E_i\cap \partial ^* E_j)=0}$.

• 3. If $\mathrm {sign}(a_i)=-\mathrm {sign}(a_j)$ and $E_i\subset E_j$, then it holds again that ${\mathcal {H}^1(\partial ^* E_i\cap \partial ^* E_j)=0}$.

We hence deduce that for every $b\in \mathbb {R}^N$ such that

$$\begin{aligned} \forall i\in \{1,\ldots ,N\},~\mathrm {sign}(a_i)=\mathrm {sign}(b_i)\,, \end{aligned}$$

we have:

$$\begin{aligned} \left| \mathrm {D}\left( \sum \limits _{i=1}^N b_i\,\mathbf {1}_{E_i}\right) \right| (\mathbb {R}^2)=\sum \limits _{i=1}^N |b_i|\,P(E_i)\,. \end{aligned}$$

(27)

This shows that if $E^{[k+1]}=(E_1,\ldots ,E_N)$ and

$$\begin{aligned} \begin{aligned} a^{[k+1]}\in ~&\underset{b \in \mathbb {R}^N}{\text {Argmin}}&\frac{1}{2}||\Phi _E\,b -y||^2+\lambda \,\sum \limits _{i=1}^N P(E_i)\,|b_i| \\&\text {s.t.}&\forall i\in \{1,\ldots ,N\},~\mathrm {sign}(b_i)=\mathrm {sign}(a_i)\,, \end{aligned} \end{aligned}$$

(28)

then, defining $u^{[k+1]}=\sum _{i=1}^N a_i^{[k+1]}\,\mathbf {1}_{E_i^{[k+1]}}$, we finally obtain ${T_{\lambda }(u^{[k+1]})\le T_{\lambda }(\tilde{u}^{[k+1]})}$, which ensures the validity of this update.

As a final note, let us mention that applying the decomposition mentioned in Sect. 2.1 to the level sets of $\tilde{u}^{[k+1]}$ is a computationally challenging task. However, we stress again that, generically, $\mathcal {H}^1(\partial ^*E_i\cap \partial ^*E_j)=0$ for every $i\ne j$, so that the above procedure is never required in practice.

C Existence of Maximizers of the Cheeger Ratio Among Simple Polygons with At Most n Sides

Let $\eta \in \mathrm {L}^2(\mathbb {R}^2)\cap C^0(\mathbb {R}^2)$ and $n\ge 3$. We want to prove the existence of maximizers of the Cheeger ratio $\mathcal {J}$ associated with $\eta$ among simple polygons with at most n sides. We will in fact prove a slightly stronger result, namely the existence of maximizers of a relaxed energy which coincides with $\mathcal {J}$ on simple polygons, and the existence of a simple polygon maximizing this relaxed energy.

We first begin by defining relaxed versions of the perimeter and the (weighted) area. To be able to deal with polygons with a number of vertices smaller than n, which will be useful in the following, we define for all $m\ge 2$ and ${x\in \mathbb {R}^{m\times 2}}$ the following quantities:

where $\chi _x(y)$ denotes the index (or winding number) of any parametrization of the polygonal curve ${[x_1,x_2],\ldots ,[x_m,x_1]}$ around $y\in \mathbb {R}^2$. In particular, for every $x\in \mathcal {X}_m$ (i.e. for every ${x\in \mathbb {R}^{m\times 2}}$ defining a simple polygon), we have

$$\begin{aligned} \mathcal {P}(x)=P(E_x) ~~\text {and}~~ \left| \mathcal {A}(x)\right| =\left| \int _{E_x}\eta \right| , \end{aligned}$$

and hence, as soon as $\mathcal {P}(x)>0$:

$$\begin{aligned} \mathcal {J}(E_x)=\frac{|\mathcal {A}(x)|}{\mathcal {P}(x)}\,. \end{aligned}$$

This naturally leads us to define

and to denote, abusing notation, $\mathcal {J}(x)=\left| \mathcal {A}(x)\right| /\mathcal {P}(x)$ for every ${x\in \mathcal {Y}_m}$.

The function $\chi _x$ is constant on each connected component of $\mathbb {R}^2\setminus \Gamma _x$ with . It takes values in ${\{- m,\ldots ,m\}}$ and is equal to zero on the only unbounded connected component. We also have ${\partial \,\text {supp}(\chi _x)\subset \Gamma _x}$. Moreover, $\chi _x$ has bounded variation and for $\mathcal {H}^1$-almost every ${y\in \Gamma _x}$ there exists $u_{\Gamma }^+(y),u_{\Gamma }^-(y)$ in $\{-m,\ldots ,m\}$ such that

Now, we define

If $\eta =0$, then the existence of maximizers is trivial. Otherwise, there exists a Lebesgue point $x_0$ of $\eta$ at which $\eta$ is nonzero. Now, the family of regular n-gons inscribed in any circle centred at $x_0$ has bounded eccentricity. Hence, if $x_{n,r}$ defines a regular n-gon inscribed in a circle of radius r centred at $x_0$, Lebesgue differentiation theorem ensures that

$$\begin{aligned} \underset{r\rightarrow 0^+}{\text {lim}}~\frac{\left| \int _{E_{x_{n,r}}}\eta \right| }{|E_{x_{n,r}}|}>0\,, \end{aligned}$$

and the fact that $\alpha >0$ easily follows.

Lemma 3

Let $C>0$. There exists $R>0$ and $c>0$ such that

$$\begin{aligned} \forall x\in \mathcal {Y}_n,~ \mathcal {J}(x)\ge C\implies \mathcal {P}(x)\ge c \text { and } \Vert x_i\Vert \le R \text { for all } i. \end{aligned}$$

Proof

The proof is similar to that of Lemma 1.

Upper bound on the perimeter: the integrability of $\eta ^2$ yields that for every $\epsilon >0$ there exists $R_1>0$ such that

$$\begin{aligned} \int _{\mathbb {R}^2\setminus B(0,R_1)}\eta ^2\le \epsilon ^2\,. \end{aligned}$$

(29)

Let $\epsilon >0$ and $R_1>0$ such that (29) holds. We have

$$\begin{aligned} \begin{aligned} \mathcal {P}(x)&\le \frac{1}{C}\left| \mathcal {A}(x)\right| \\&\le \frac{1}{C}\left[ \left| \int _{\mathbb {R}^2\cap B(0,R)}\eta \,\chi _x\right| +\left| \int _{\mathbb {R}^2\setminus B(0,R)}\eta \,\chi _x\right| \right] \\&\le \frac{1}{C}\left[ \Vert \eta \Vert _{\mathrm {L}^2}\,\Vert \chi _x\Vert _{\mathrm {L}^\infty }\,\sqrt{|B(0,R)|}+\epsilon \,\Vert \chi _x\Vert _{\mathrm {L}^2}\right] \\&\le \frac{1}{C}\left[ \Vert \eta \Vert _{\mathrm {L}^2}\,n\,\sqrt{|B(0,R)|}+\epsilon \,\frac{1}{\sqrt{c_2}}|\mathrm {D}\chi _x|(\mathbb {R}^2)\right] \\&\le \frac{1}{C}\left[ \Vert \eta \Vert _{\mathrm {L}^2}\,n\,\sqrt{|B(0,R)|}+\epsilon \,\frac{2n}{\sqrt{c_2}} \mathcal {P}(x)\right] . \end{aligned} \end{aligned}$$

Now, taking

we finally get that ${\mathcal {P}(x)\le c'}$.

Inclusion in a ball: we take $\epsilon =\frac{\sqrt{c_2}}{4n}$ and fix ${R_2>0}$ such that $\int _{\mathbb {R}^2\setminus B(0,R_2)}\eta ^2\le \epsilon ^2$. Let us show that

$$\begin{aligned} \text {supp}(\chi _x)\cap B(0,R_2)\ne \emptyset \,. \end{aligned}$$

By contradiction, if $\text {supp}(\chi _x)\cap B(0,R_2)= \emptyset$, we would have:

$$\begin{aligned} \begin{aligned} \mathcal {P}(x)&\le \frac{1}{C}\left| \mathcal {A}(x)\right| \\&=\frac{1}{C} \left| \int _{\mathbb {R}^2\setminus B(0,R_2)}\eta \,\chi _x\right| \\&\le \sqrt{\int _{\mathbb {R}^2\setminus B(0,R_2)}\eta ^2}~\Vert \chi _x\Vert _{\mathrm {L}^2}\\&\le \frac{\epsilon }{\sqrt{c_2}}|D\chi _x|(\mathbb {R}^2)\le \frac{2n\,\epsilon }{\sqrt{c_2}}\,\mathcal {P}(x)\,. \end{aligned} \end{aligned}$$

Dividing by $\mathcal {P}(x)>0$ yields a contradiction. Now, since

$$\begin{aligned} \partial \, \text {supp}(\chi _x)\subset \Gamma _x\,, \end{aligned}$$

we have $\text {diam}(\text {supp}(\chi _x))\le \mathcal {P}(x)\le c'$ which shows

This in turn implies that $\Vert x_i\Vert \le R$ for all i.

Lower bound on the perimeter: the integrability of $\eta ^2$ shows that, for every $\epsilon >0$, there exists $\delta >0$ such that

$$\begin{aligned} \forall E\subset \mathbb {R}^2,~|E|\le \delta \implies \left| \int _{E}\eta ^2\right| \le \epsilon ^2\,. \end{aligned}$$

Taking , we obtain that if $|\text {supp}(\chi _x)|\le \delta$

$$\begin{aligned} \begin{aligned} \mathcal {P}(x)&\le \frac{1}{C}\left| \mathcal {A}(x)\right| =\frac{1}{C}\left| \int _{\text {supp}(\chi _x)}\eta \right| \\&\le \frac{1}{C}\sqrt{\int _{\text {supp}( \chi _x)}\eta ^2}~\sqrt{|\text {supp}(\chi _x)|}\\&\le \frac{\epsilon }{C\sqrt{c_2}}\,P(\text {supp}(\chi _x))\\&\le \frac{\epsilon }{C\sqrt{c_2}}\,\mathcal {P}(x)\,, \end{aligned} \end{aligned}$$

the last inequality holding because $\partial \,\text {supp}(\chi _x)\subset \Gamma _x$. We get a contradiction since $\mathcal {P}(x)$ is positive. $\square$

Applying Lemma 3 with, e.g. $C=\alpha /2$, and defining

we see that any maximizer of $\mathcal {J}$ over $\mathcal {Y}'_n$ (if it exists) is also a maximizer of $\mathcal {J}$ over $\mathcal {Y}_n$, and conversely.

Lemma 4

Let $x\in \mathbb {R}^{n\times 2}$. Then, for every $a\in \mathbb {R}^2$ we have

$$\begin{aligned} \begin{aligned}&\mathcal {A}(x)=\sum \limits _{i=1}^n\mathrm {sign}(\mathrm {det}(x_i-a~x_{i+1}-a))\int _{a x_i x_{i+1}}\eta \\&=\sum \limits _{i=1}^n \mathrm {det}(x_i-a~x_{i+1}-a)\int _{T_1}\eta ((x_i-a~x_{i+1}-a)\,y)\,\mathrm{d}y\,, \end{aligned} \end{aligned}$$

where $a x_i x_{i+1}$ denotes the triangle with vertices $a,x_i,x_{i+1}$ and is the unit triangle.

Proof

Let us show that for all ${a\in \mathbb {R}^2}$ we have

$$\begin{aligned} \chi _x=\sum \limits _{i=1}^n\mathrm {sign}(\mathrm {det}(x_i-a~x_{i+1}-a))\,\mathbf {1}_{a x_i x_{i+1}} \end{aligned}$$

(30)

almost everywhere. First, we have that $y\in \mathbb {R}^2$ is in the (open) triangle $ax_ix_{i+1}$ if and only if the ray issued from y directed by $y-a$ intersects $]x_i,x_{i+1}[$. Moreover, if y is in this triangle, then

$$\begin{aligned} \text {sign}(\text {det}(x_i-a~x_{i+1}-a))=\text {sign}\left( (y-a)\cdot (x_{i+1}-x_i)^{\perp }\right) . \end{aligned}$$

The above hence shows that, if $y\in \mathbb {R}^2\setminus \cup _{i=1}^n[x_i,x_{i+1}]$ does not belong to any of the segments $[a,x_i]$, evaluating the right hand side of (30) at y amounts to computing the winding number $\chi _x(y)$ by applying the ray-crossing algorithm described in [24]. This in particular means that (30) holds almost everywhere, and the result follows. $\square$

From Lemma 4, we deduce that $\mathcal {A}$ is continuous on $\mathbb {R}^{n\times 2}$. This is also the case of $\mathcal {P}$. Now, $\mathcal {Y}'_n$ is compact and included in $\mathcal {Y}_n$, hence the existence of maximizers of $\mathcal {J}$ over $\mathcal {Y}'_n$, which in turn implies the existence of maximizers of $\mathcal {J}$ over $\mathcal {Y}_n$.

Let us now show there exists a maximizer which belongs to $\mathcal {X}_n$. To do so, we rely on the following lemma

Lemma 5

Let $m\ge 3$ and $x\in \mathcal {Y}_m\setminus \mathcal {X}_m$. Then, there exists $m'$ with $2\le m'<m$ and $y\in \mathcal {Y}_{m'}$ such that

$$\begin{aligned} \mathcal {J}(x)\le \mathcal {J}(y)\,. \end{aligned}$$

Proof

If $x\in \mathcal {Y}_m\setminus \mathcal {X}_m$, then $[x_1,x_2],\ldots ,[x_m,x_1]$ is not simple. If there exists i with $x_i=x_{i+1}$, then

$$\begin{aligned} y=(x_1,\ldots ,x_i,x_{i+2},\ldots ,x_m) \end{aligned}$$

is suitable, and likewise if $x_1=x_m$, then

$$\begin{aligned} y=(x_1,\ldots ,x_{m-1}) \end{aligned}$$

is suitable. Otherwise, we distinguish the following cases:

If there exists $i<j$ with $x_i=x_j$: we define

$$\begin{aligned} \begin{aligned} y&=(x_1,\ldots ,x_i,x_{j+1},\ldots ,x_m)\in \mathbb {R}^{m-(j-i)}\,,\\ z&=(x_i,x_{i+1},\ldots ,x_{j-1})\in \mathbb {R}^{j-i}\,. \end{aligned} \end{aligned}$$

We notice that $2\le j-i<m$ and $2\le m-(j-i)<m$.

If there exists $i<j$ with $x_i\in ]x_j,x_{j+1}[$: we necessarily have $(i,j)\ne (1,m)$. We define

$$\begin{aligned} \begin{aligned} y&=(x_1,\ldots ,x_i,x_{j+1},\ldots ,x_m)\in \mathbb {R}^{m-(j-i)}\,,\\ z&=(x_i,x_{i+1},\ldots ,x_{j})\in \mathbb {R}^{j-i+1}\,. \end{aligned} \end{aligned}$$

We again have $2\le m-(j-i)<m$, and since $(i,j)\ne (1,m)$, we have $j-i<m-1$ which shows $2\le j-i+1<m$.

If there exists $i<j$ with $x_j\in ]x_i,x_{i+1}[$: we necessarily have $j>i+1$. We define

$$\begin{aligned} \begin{aligned} y&=(x_1,\ldots ,x_i,x_j,\ldots ,x_m)\in \mathbb {R}^{m-(j-i)+1}\,,\\ z&=(x_{i+1},\ldots ,x_{j})\in \mathbb {R}^{j-i}\,. \end{aligned} \end{aligned}$$

We again have $2\le j-i<m$, and since $j>i+1$ we obtain that $2\le {m-(j-i)+1<m}$.

If there exists $i<j$ with $x'\in ]x_i,x_{i+1}[\,\cap \,]x_j,x_{j+1}[$: if we have $j=i+1$, then either $x_{i+2}\in ]x_i,x_{i+1}[$ or $x_i\in ]x_{i+1},x_{i+2}[$ and in both cases we fall back on the previously treated cases. The same holds if $(i,j)=(1,m)$. Otherwise, we define

$$\begin{aligned} \begin{aligned} y&=(x_1,\ldots ,x_i,x',x_{j+1},\ldots ,x_m)\in \mathbb {R}^{m-(j-i)+1}\,,\\ z&=(x',x_{i+1},\ldots ,x_{j})\in \mathbb {R}^{j-i+1}\,. \end{aligned} \end{aligned}$$

Since $j>i+1$ and $(i,j)\ne (1,m)$, we get $2\le m-(j-i)+1<m$ and $2\le j-i+1<m$.

Now, one can see that in each case we have ${\mathcal {P}(x)=\mathcal {P}(y)+\mathcal {P}(z)}$ and $\chi _x=\chi _y+\chi _z$ almost everywhere, which in turn gives that ${\mathcal {A}(x)=\mathcal {A}(y)+\mathcal {A}(z)}$. We hence get that $\mathcal {P}(y)=0$ or $\mathcal {P}(z)=0$, and in this case $\mathcal {J}(x)=\mathcal {J}(y)$ or $\mathcal {J}(x)=\mathcal {J}(z)$, or that $\mathcal {P}(y)>0$ and $\mathcal {P}(z)>0$, which yields

$$\begin{aligned} \begin{aligned} \frac{\left| \mathcal {A}(x)\right| }{\mathcal {P}(x)}&\le \frac{\left| \mathcal {A}(y)\right| +\left| \mathcal {A}(z)\right| }{\mathcal {P}(y)+\mathcal {P}(z)}\\&=\frac{\mathcal {P}(y)}{\mathcal {P}(y)+\mathcal {P}(z)} \frac{\left| \mathcal {A}(y)\right| }{\mathcal {P}(y)}+ \frac{\mathcal {P}(z)}{\mathcal {P}(y)+\mathcal {P}(z)} \frac{\left| \mathcal {A}(z)\right| }{\mathcal {P}(z)}\,. \end{aligned} \end{aligned}$$

Hence, $\mathcal {J}(x)$ is smaller than a convex combination of $\mathcal {J}(y)$ and $\mathcal {J}(z)$, which gives that it is smaller than $\mathcal {J}(y)$ or $\mathcal {J}(z)$. This shows that y or z is suitable. $\square$

We can now prove our final result, i.e. that there exists ${x_*\in \mathcal {X}_n}$ such that

$$\begin{aligned} \forall x\in \mathcal {Y}_n,~\mathcal {J}(x_*)\ge \mathcal {J}(x)\,. \end{aligned}$$

Indeed, repeatedly applying the above lemma starting with a maximizer $x_*$ of $\mathcal {J}$ over $\mathcal {Y}_n$, we either have that there exists m with $3\le m\le n$ and ${x'_*\in \mathcal {X}_m}$ such that $\mathcal {J}(x_*)=\mathcal {J}(x'_*)$, or that there exists $y\in \mathcal {Y}_2$ such that $\mathcal {J}(x_*)\le \mathcal {J}(y)$, which is impossible since in that case $\mathcal {J}(y)=0$ and $\mathcal {J}(x_*)=\alpha >0$. We hence have $x'_*\in \mathcal {X}_m$ such that

$$\begin{aligned} \forall x\in \mathcal {Y}_n,~\mathcal {J}(x'_*)=\mathcal {J}(x_*)\ge \mathcal {J}(x)\,. \end{aligned}$$

We can finally build $x''_*\in \mathcal {X}_n$ such that $\mathcal {J}(x''_*)=\mathcal {J}(x'_*)$ by adding dummy vertices to $x'_*$, which finally allows to conclude.

D Proof of Proposition 6

First, let us stress that for any function v that is piecewise constant on $(C_{i,j})_{(i,j)\in [ 1,N]^2}$ and that is equal to 0 outside ${[-R,R]^2}$, we have $J(v)=h\,\Vert \nabla ^h v\Vert _{1,1}$ where by abuse of notation $\nabla ^h v$ is given by (16) with $v_{i,j}$ the value of v in $C_{i,j}$. Hence, $J^h(u^h) \le 1$ for all h implies that $J(u^h)$ (and hence $\Vert u^h\Vert _{\mathrm {L}^2}$) is uniformly bounded in h. There hence exists a (not relabeled) subsequence that converges strongly in $\mathrm {L}^1_{loc}(\mathbb {R}^2)$ and weakly in $\mathrm {L}^2(\mathbb {R}^2)$ to a function u, with moreover $\mathrm {D}u^h\overset{*}{\rightharpoonup }\mathrm {D}u$.

Let us now take $\phi =(\phi ^{(1)},\phi ^{(2)})\in C^{\infty }_c(\mathbb {R}^2,\mathbb {R}^2)$ such that ${||\phi ||_{\infty }\le 1}$. The weak-* convergence of the gradients gives us that

$$\begin{aligned} \begin{aligned}&\int _{\mathbb {R}^2}\phi \cdot \mathrm{d}Du =\underset{h\rightarrow 0}{\text {lim}}~\int _{\mathbb {R}^2}\phi \cdot \mathrm{d}Du^h\\ =&\underset{h\rightarrow 0}{\text {lim}}~\sum \limits _{i=0}^N\sum \limits _{j=0}^N \begin{pmatrix}\int _{C^h_{i,j}\cap C^h_{i+1,j}}\phi ^{(1)}\,\mathrm{d}\mathcal {H}^1\\ \int _{C^h_{i,j}\cap C^h_{i,j+1}}\phi ^{(2)}\,\mathrm{d}\mathcal {H}^1\end{pmatrix}\cdot \nabla ^h u^h_{i,j}\,. \end{aligned} \end{aligned}$$

One can moreover show there exists $C>0$ such that for h small enough and all (i, j), we have:

$$\begin{aligned} \begin{aligned}&\left| \left[ \int _{C^h_{i,j}\cap C^h_{i+1,j}}\phi ^{(1)}\,\mathrm{d} \mathcal {H}^1\right] -h\,\phi ^{(1)}(x^h_{i+1,j+1})\right| \le Ch^2\,,\\&\left| \left[ \int _{C^h_{i,j}\cap C^h_{i,j+1}}\phi ^{(2)}\,\mathrm{d} \mathcal {H}^1\right] -h\,\phi ^{(2)}(x^h_{i+1,j+1})\right| \le Ch^2\,,\\ \end{aligned} \end{aligned}$$

with . We use the above inequalities and the fact $\Vert \phi (x)\Vert \le 1$ for all x to obtain the existence of $C'>0$ such that for h small enough and for all (i, j) we have:

$$\begin{aligned} \left\| \begin{pmatrix}\int _{C^h_{i,j}\cap C^h_{i+1,j}}\phi ^{(1)}\,\mathrm{d}\mathcal {H}^1\\ \int _{C^h_{i,j}\cap C^h_{i,j+1}}\phi ^{(2)}\,\mathrm{d}\mathcal {H}^1\end{pmatrix}\right\| _2\le h\,\sqrt{1+C'h}\,. \end{aligned}$$

This finally yields

$$\begin{aligned}\begin{aligned}&\sum \limits _{i=0}^N\sum \limits _{j=0}^N \begin{pmatrix}\int _{C^h_{i,j}\cap C^h_{i+1,j}}\phi ^{(1)}\,\mathrm{d}\mathcal {H}^1\\ \int _{C^h_{i,j}\cap C^h_{i,j+1}}\phi ^{(2)}\,\mathrm{d}\mathcal {H}^1\end{pmatrix}\cdot \nabla ^h u^h_{i,j}\\ \le&\sum \limits _{i=0}^N\sum \limits _{j=0}^N h\,\sqrt{1+C'h} ~\Vert \nabla ^h u^h_{i,j}\Vert =\sqrt{1+C'h}~J^h(u^h)\,, \end{aligned} \end{aligned}$$

which gives

$$\begin{aligned} \int _{\mathbb {R}^2}\phi \cdot \mathrm{d}Du\le \underset{h\rightarrow 0}{\text {lim sup}}~ \sqrt{1+C'h}~J^h(u^h)\le 1\,. \end{aligned}$$

We now have to show that

$$\begin{aligned} \forall v\in \mathrm {L}^2(\mathbb {R}^2),~J(v)\le 1\implies \int _{\mathbb {R}^2}\eta \,u\le \int _{\mathbb {R}^2}\eta \,v\,. \end{aligned}$$

Let $v\in C^{\infty }([-R,R]^2)$ be such that $J(v)\le 1$. We define

One can then show that

$$\begin{aligned} \underset{h\rightarrow 0}{\text {lim}}~J^h(v^h)=J(v)=1\,, \end{aligned}$$

so that for every $\delta >0$ we have ${J^h\left( \frac{v^h}{1+\delta }\right) \le 1}$ for h small enough. Now, this yields

$$\begin{aligned} \begin{aligned} \int _{[-R,R]^2}\eta \,u&=\underset{h\rightarrow 0}{\text {lim}}~\int _{[-R,R]^2}\eta \,u^h\\&\le \underset{h\rightarrow 0}{\text {lim}}~\int _{[-R,R]^2}\eta \,\frac{v^h}{1+\delta }\\&=\int _{[-R,R]^2}\eta \,\frac{v}{1+\delta }\,. \end{aligned} \end{aligned}$$

Since this holds for all $\delta >0$, we get that

$$\begin{aligned} \int _{[-R,R]^2}\eta \,u\le \int _{[-R,R]^2}\eta \,v\,. \end{aligned}$$

(31)

Finally, if $v\in \mathrm {L}^2(\mathbb {R}^2)$ is such that $v=0$ outside $[-R,R]^2$ and ${J(v)\le 1}$, by standard approximation results (see [4, remark 3.22]), we also have that (31) holds, and hence, u solves (6). Finally, since u solves (6), its support is included in $[-R,R]^2$, which shows the strong $\mathrm {L}^1_{loc}(\mathbb {R}^2)$ convergence of $(u^h)$ towards $u^*$ in fact implies its strong $\mathrm {L}^1(\mathbb {R}^2)$ convergence.

E First Variation of the Perimeter and Weighted Area Functionals for Simple Polygons

We stress that since $\mathcal {X}_n$ is open, for every ${x\in \mathcal {X}_n}$ the functions ${h\mapsto P(E_{x+h})}$ and $h\mapsto \int _{E_{x+h}}\eta$ are well-defined in a neighbourhood of zero (for any locally integrable function $\eta$). We now compute the first variation of these two quantities.

Proposition 15

Let $x\in \mathcal {X}_n$. Then, we have

$$\begin{aligned} P(E_{x+h})=P(E_x)-\sum \limits _{i=1}^n \left\langle h_i,\tau _i-\tau _{i-1}\right\rangle + o\left( \Vert h\Vert \right) , \end{aligned}$$

(32)

where is the unit tangent vector to $[x_i,x_{i+1}]$.

Proof

If $\Vert h\Vert$ is small enough, we have:

$$\begin{aligned} \begin{aligned}&P(E_{x+h})=\sum \limits _{i=1}^n\Vert x_{i+1}-x_i+h_{i+1}-h_i\Vert \\&\quad =\sum \limits _{i=1}^n\sqrt{\Vert x_{i+1}-x_i+h_{i+1}-h_{i}\Vert ^2}\\&\quad =\sum \limits _{i=1}^n\Vert x_{i+1}-x_i\Vert \\&\qquad \times \left( 1+\frac{\langle x_{i+1}-x_i,h_{i+1}-h_i\rangle }{\Vert x_{i+1}-x_i\Vert ^2}+o\left( \Vert h\Vert \right) \right) \\&\quad =~P(E_x)+\sum \limits _{i=1}^n\langle \tau _i,h_{i+1}-h_i\rangle +o\left( \Vert h\Vert \right) ,\\ \end{aligned} \end{aligned}$$

and the result follows by re-arranging the terms in the sum. $\square$

Proposition 16

Let $x\in \mathcal {X}_n$ and $\eta \in C^0(\mathbb {R}^2)$. Then, we have

$$\begin{aligned} \int _{E_{x+h}}\eta =\int _{E_x}\eta +\sum \limits _{i=1}^n \left\langle h_i,w_i^-\nu _{i-1}+w_i^+\nu _i\right\rangle + o\left( \Vert h\Vert \right) ,\nonumber \\ \end{aligned}$$

(33)

where $\nu _i$ is the outward unit normal to $E_x$ on $]x_i,x_{i+1}[$ and

Proof

Our proof relies on the following identity (see Lemma 4 for a proof of a closely related formula):

$$\begin{aligned} \int _{E_x}\eta =\text {sign}\left( \sum \limits _{i=1}^n \det (x_i~x_{i+1})\right) \sum \limits _{i=1}^n \omega (x_i,x_{i+1})\,, \end{aligned}$$

with

where is the unit triangle. Assuming $\eta \in C^1(\mathbb {R}^2)$ and denoting $\mathrm {adj}(A)$ the adjugate of a matrix A, we have:

$$\begin{aligned} \begin{aligned}&\omega (a_1+h_1,a_2+h_2) =~\omega (a_1,a_2)+\mathrm {det}(a_1~a_2)\\&\qquad \times \int _{T_1}\nabla \eta ((a_1~a_2)\,y)\cdot ((h_1~h_2)y)\,\mathrm{d}y\\&\qquad +~\mathrm {tr}\left( \mathrm {adj}(a_1~a_2)^T(h_1~h_2)\right) \\&\qquad \times \int _{T_1}\eta ((a_1~a_2)\,y)\,\mathrm{d}y+o(\Vert h\Vert )\\&\quad =~\omega (a_1,a_2)+\mathrm {sign}(\mathrm {det}(a_1~a_2))\\&\qquad \times \int _{Oa_1a_2}\nabla \eta (y)\cdot ((h_1~h_2)\,(a_1~a_2)^{-1})\,y)\,\mathrm{d}y\\&\qquad +\frac{\mathrm {tr}\left( \mathrm {adj}(a_1~a_2)^T(h_1~h_2) \right) }{|\mathrm {det}(a_1~a_2)|}\\&\qquad \times \int _{Oa_1 a_2}\eta (y)\,\mathrm{d}y+o(\Vert h\Vert )\,. \end{aligned} \end{aligned}$$

Denoting , we obtain:

$$\begin{aligned} \begin{aligned}&\omega (a_1+h_1,a_2+h_2)\\&\quad =~\omega (a_1,a_2)+\mathrm {sign}(\mathrm {det}(a_1~a_2))\\&\qquad \int _{Oa_1a_2}\left[ \nabla \eta \cdot g+\eta \,\mathrm {div}g\right] +o(\Vert h\Vert )\\&\quad =\omega (a_1,a_2)+\mathrm {sign}(\mathrm {det}(a_1~a_2))\\&\qquad \int _{\partial (Oa_1a_2)}\eta \,(g\cdot \nu _{Oa_1a_2})\,d\mathcal {H}^1+o(\Vert h\Vert )\,, \end{aligned} \end{aligned}$$

where we used Gauss–Green theorem to obtain the last equality. Now, if $\Vert h\Vert$ is small enough, then

$$\begin{aligned} \sum \limits _{i=1}^n\det (x_i+h_i~~x_{i+1}+h_{i+1}) ~\text {and}~ \sum \limits _{i=1}^n\det (x_i~x_{i+1}) \end{aligned}$$

have the same sign, so that, defining

$$\begin{aligned} g_i:y\mapsto ((h_i~h_{i+1})(x_i~x_{i+1})^{-1}\,y)\,, \end{aligned}$$

we get

$$\begin{aligned} d\left( \int _{E_{\bullet }}\eta \right) (x)\,.\,h=\epsilon \sum \limits _{i=1}^n\mathrm {sign}(\mathrm {det}(x_i~x_{i+1}))~\omega _i\,, \end{aligned}$$

with

Then, one can decompose each integral in the sum and show the integrals over $[0,x_i]$ cancel out each other, which allows to obtain

$$\begin{aligned} d\left( \int _{E_{\bullet }}\eta \right) (x)\,.\,h=\sum \limits _{i=1}^n\int _{[x_i,x_{i+1}]} \eta \,(g_i\cdot \nu _i)\,\mathrm{d}\mathcal {H}^1\,. \end{aligned}$$

But now if $y\in [x_i,x_{i+1}]$, then

$$\begin{aligned} (x_i~x_{i+1})^{-1}y=\frac{1}{\Vert x_{i+1}-x_i\Vert } \begin{pmatrix}\Vert y-x_{i+1}\Vert \\ \Vert y-x_i\Vert \end{pmatrix}\,, \end{aligned}$$

and the result follows by re-arranging the terms in the sum. One can then use an approximation argument as in [27, Proposition 17.8] to show it also holds when $\eta$ is only continuous. $\square$

F Results Used in Section 7

1.1 F.1 Properties of the Radialisation Operator

The goal of this subsection, based on [18, II.1.4], is to prove the following result:

Proposition 17

Let $u\in \mathrm {L}^2(\mathbb {R}^2)$ be s.t. ${|\mathrm {D}u|(\mathbb {R}^2)<+\infty }$. Then, ${|\mathrm {D}\tilde{u}|(\mathbb {R}^2)\le |\mathrm {D}u|(\mathbb {R}^2)}$ with equality if and only if u is radial.

First, one can show that for every $u\in \mathrm {L}^2(\mathbb {R}^2)$, the radialisation $\tilde{u}$ of u defined in Sect. 7 by

$$\begin{aligned} \tilde{u}(x)=\int _{\mathbb {S}^1}u(\Vert x\Vert \,e)\,\mathrm{d}\mathcal {H}^1(e) \end{aligned}$$

(34)

is well defined and belongs to $\mathrm {L}^2(\mathbb {R}^2)$. Then, a change of variables in polar coordinates shows that, as stated in the following lemma, the radialisation operator is self-adjoint.

Lemma 6

We have

$$\begin{aligned} \forall u,v\in \mathrm {L}^2(\mathbb {R}^2),~\int _{\mathbb {R}^2}\tilde{u}(x)\,v(x)\,\mathrm{d}x=\int _{\mathbb {R}^2}u(x)\,\tilde{v}(x)\,\mathrm{d}x\,. \end{aligned}$$

We now state a useful identity:

Lemma 7

For every $\varphi \in C^{\infty }_c(\mathbb {R}^2\setminus \{0\},\mathbb {R}^2)$, we have:

$$\begin{aligned} \left\langle \mathrm {D}\tilde{u},\varphi \right\rangle =\left\langle \mathrm {D}u,\widetilde{\varphi \cdot \frac{x}{\Vert x\Vert }}\right\rangle , \end{aligned}$$

where $\varphi \cdot \frac{x}{\Vert x\Vert }$ denotes the mapping $x\mapsto \left( \varphi (x)\cdot \frac{x}{\Vert x\Vert }\right)$.

Proof

From Lemma 6, we get

$$\begin{aligned} \left\langle \mathrm {D}\tilde{u},\varphi \right\rangle =\int _{\mathbb {R}^2}\tilde{u}\, \mathrm {div}\varphi =\int _{\mathbb {R}^2}u\,\widetilde{\mathrm {div}\varphi }\,. \end{aligned}$$

Using polar coordinates, defining

we get

$$\begin{aligned} \begin{aligned} \left( \mathrm {div}\varphi \right) (h(r,\theta ))=&~~~~\frac{1}{r}\frac{\partial }{\partial r}(r(\varphi _r \circ h))(r,\theta )\\&\,+\frac{1}{r}\frac{\partial }{\partial \theta }(\varphi _{\theta } \circ h)(r,\theta )\,, \end{aligned} \end{aligned}$$

(35)

where $\varphi _r$ and $\varphi _{\theta }$, respectively, denote the radial and orthoradial components of $\varphi$, i.e.

$$\begin{aligned} \varphi _r(x)=\varphi (x)\cdot \frac{x}{\Vert x\Vert } \text { and }\varphi _{\theta }(x)=\varphi (x)\cdot \frac{x^{\perp }}{\Vert x\Vert }\,. \end{aligned}$$

The second term in (35) has zero circular mean. Interchanging derivation and integration, we get that the radialisation of the first term equals $\frac{1}{r}\frac{\partial }{\partial r}\left( r\left( \widetilde{\varphi _r}\circ h\right) \right)$, which yields

$$\begin{aligned} \left( \widetilde{\mathrm {div}\varphi }\right) (x)=\mathrm {div}\left( \widetilde{\varphi \cdot \frac{x}{\Vert x\Vert }}\right) (x)\,. \end{aligned}$$

$\square$

We now introduce the radial and orthoradial components of the gradient, which are Radon measures on  defined by

$$\begin{aligned} \begin{aligned} \forall \psi \in C^{\infty }_c(U),~\left\langle \mathrm {D}_{\mathrm {rad}}u, \psi \right\rangle&=\left\langle \mathrm {D}u ,\psi \,\frac{x}{|x|}\right\rangle ,\\ \left\langle \mathrm {D}_{\mathrm {orth}}u,\psi \right\rangle&=\left\langle \mathrm {D}u ,\psi \,\frac{x^\perp }{|x|}\right\rangle . \end{aligned} \end{aligned}$$

Proposition 18

There exist two $|\mathrm {D}u|$-measurable mappings from U to $\mathbb {R}$, denoted $g_{\mathrm {rad}}$ and $g_{\mathrm {orth}}$, such that

$$\begin{aligned} g_{\mathrm {rad}}^2+g_{\mathrm {orth}}^2\le 1~|\mathrm {D}u|\text {-almost everywhere} \end{aligned}$$

and

$$\begin{aligned} \begin{aligned} \forall \psi \in C^{\infty }_c(U),~\langle \mathrm {D}_{\mathrm {rad}}u,\psi \rangle&=\int _U \psi (x)\,g_{\mathrm {rad}}(x)\,\mathrm{d}|\mathrm {D}u|(x)\,, \\ \langle \mathrm {D}_{\mathrm {orth}}u,\psi \rangle&=\int _U \psi (x)\,g_{\mathrm {orth}}(x)\,\mathrm{d}|\mathrm {D}u|(x)\,. \end{aligned} \end{aligned}$$

(36)

Proof

The existence of the $|\mathrm {D}u|$-measurable mappings $g_{\mathrm {rad}}$ and $g_{\mathrm {orth}}$, as well as (36), come from Lebesgue differentiation theorem, and the fact $\mathrm {D}_{\mathrm {rad}}u$ and $\mathrm {D}_{\mathrm {orth}}u$ are absolutely continuous with respect to $\mathrm {D}u$. Now, for every open set $A\subset U$ we have:

$$\begin{aligned} \begin{aligned} |\mathrm {D}u|(A)&=\sup \left\{ \left\langle \mathrm {D}u,\varphi \right\rangle \,\big |\,\varphi \in C^{\infty }_c(A,\mathbb {R}^2),~\Vert \varphi \Vert _{\infty }\le 1\right\} \\&=\sup \bigg \{\left\langle \mathrm {D}u,\varphi _1\frac{x}{\Vert x\Vert }\right\rangle + \left\langle \mathrm {D}u,\varphi _2\frac{x^{\perp }}{\Vert x\Vert }\right\rangle \text { s.t.}\\&\qquad \qquad ~\varphi _i\in C^{\infty }_c(A),~\left\| \varphi _1^2+\varphi _2^2\right\| _{\infty }\le 1\bigg \}\\&=\sup \bigg \{\left\langle \mathrm {D}_{\mathrm {rad}}u,\varphi _1\right\rangle + \left\langle \mathrm {D}_{\mathrm {orth}}u,\varphi _2\right\rangle \text { s.t. }\\&\qquad \qquad ~\varphi _i\in C^{\infty }_c(A),~\left\| \varphi _1^2+\varphi _2^2\right\| _{\infty }\le 1\bigg \}\,. \end{aligned} \end{aligned}$$

Hence, for $\varphi _i\in C^{\infty }_c(A)$ such that $\left\| \varphi _1^2+\varphi _2^2\right\| _{\infty }\le 1$ we have:

$$\begin{aligned} \int _{A}1\,\mathrm{d}|\mathrm {D}u|\ge \int _{A}(g_{\mathrm {rad}}\,\varphi _1+g_{\mathrm {orth}}\,\varphi _2)\,d|\mathrm {D}u|\,. \end{aligned}$$

If we had $g_{\mathrm {rad}}^2+g_{\mathrm {orth}}^2> 1$ on a set of nonzero measure $|\mathrm {D}u|$, we would have a contradiction. $\square$

We can now prove Proposition 17. Indeed, since $\{0\}$ is $\mathcal {H}^1$-negligible, we have that

$$\begin{aligned} |\mathrm {D}u|(\{0\})=|\mathrm {D}\tilde{u}|(\{0\})=0\,, \end{aligned}$$

and moreover

$$\begin{aligned} |\mathrm {D}\tilde{u}|(\mathbb {R}^2\setminus \{0\})\le |\mathrm {D}_{\mathrm {rad}}u|(\mathbb {R}^2\setminus \{0\})\le |\mathrm {D}u|(\mathbb {R}^2\setminus \{0\})\,. \end{aligned}$$

(37)

The first equality comes from Lemma 7, while the second is easily obtained from the definition of $\mathrm {D}_{\mathrm {rad}}$. Now, if we have ${|\mathrm {D}_{\mathrm {rad}}u|(U)=|\mathrm {D}u|(U)}$, then we get

$$\begin{aligned} \int _{U}g_{\mathrm {rad}}\,d|\mathrm {D}u|=\int _{U}\sqrt{g_{\mathrm {rad}}^2+g_{\mathrm {orth}}^2}\,\mathrm{d}|\mathrm {D}u|=\int _{U}d|\mathrm {D}u|\,. \end{aligned}$$

This yields $g_{\mathrm {orth}}=0$ (and $|g_{\mathrm {rad}}|=1$) $|\mathrm {D}u|$-almost everywhere. Hence, $\mathrm {D}_{\mathrm {orth}}u=0$.

Let us now show this implies that u is radial. If we define , then we have that the mapping given by ${h:(r,\theta )\mapsto (r\cos \theta ,r\sin \theta )}$ is a $C^{\infty }$-diffeomorphism from A to $\mathbb {R}^2\setminus \left( \mathbb {R}_{-}\times \{0\}\right)$. Now, if $\xi \in C_c^{\infty }(A)$, we have that ${\xi \circ h^{-1}\in C_c^{\infty }(h(A))}$ and

$$\begin{aligned} \begin{aligned} 0&=\left\langle \mathrm {D}_{\mathrm {orth}}u,\xi \circ h^{-1}\right\rangle \\&= \int _{\mathbb {R}^2}u\,\mathrm {div}\left( \left( \xi \circ h^{-1}\right) \frac{x^{\perp }}{\Vert x\Vert }\right) \\&=\int _{0}^{+\infty }\int _{-\pi }^{\pi }\left( u\circ h\right) (r,\theta )\,\left( \frac{1}{r}\frac{\partial }{\partial \theta } (\xi )(r,\theta )\right) r\,\mathrm{d}\theta \,\mathrm{d}r\,. \end{aligned} \end{aligned}$$

This means that $\frac{\partial \theta }{\partial }(u\circ h)=0$ in the sense of distributions, and hence, that there exists¹³ a mapping ${g:\,]0,+\infty [\rightarrow \mathbb {R}}$ such that for almost every $(r,\theta )\in A$, $(u\circ h)(r,\theta )=g(r)$. We finally get ${u(x)=g(\Vert x\Vert )}$ for almost every $x\in h(A)$, which shows u is radial.

1.2 F.2 Lemmas Used in the Proof of Proposition 9

We take and keep the assumptions of Sect. 7.

Lemma 8

Let $f:\mathbb {R}\rightarrow \mathbb {R}_+$ be square integrable, even and decreasing on $\mathbb {R}_+$. Then, for every measurable set A such that ${|A|<+\infty }$ we have

$$\begin{aligned} \int _{A}f\le \int _{A^s}f\,, \end{aligned}$$

where . Moreover, equality holds if and only if $|A\triangle A^s|=0$.

Proof

We have

$$\begin{aligned} \int _{A}f=\int _{0}^{+\infty }\left| \left\{ f\,\mathbf {1}_A\ge t\right\} \right| \mathrm{d}t=\int _{0}^{+\infty }\left| \left\{ f\ge t\right\} \cap A\right| \mathrm{d}t\,. \end{aligned}$$

For all $t>0$, there exists $\alpha$ such that $\{f\ge t\}=[-\alpha ,\alpha ]$, so that we have

$$\begin{aligned} \begin{aligned} \left| \left\{ f\ge t\right\} \cap A\right|&=\left| [-\alpha ,\alpha ] \cap A\right| \le \text {min}(2\alpha ,|A|)\\ {}&=\left| [-\alpha ,\alpha ]\cap [-|A|/2,|A|/2]\right| \\ {}&=\left| \left\{ f\ge t\right\} \cap A^s\right| . \end{aligned} \end{aligned}$$

Hence,

$$\begin{aligned} \int _{A}f\le \int _{0}^{+\infty }\left| \left\{ f\ge t\right\} \cap A^S\right| \mathrm{d}t=\int _{A^s}f\,. \end{aligned}$$

Now, if $|A\triangle A^s|>0$, then $|A\setminus A^s|=|A^s\setminus A|>0$ and we have

$$\begin{aligned} \begin{aligned} \int _{A^s}f&=\!\int _{A\cap A^s}f+\int _{A^s\setminus A}f \!>\!\int _{A\cap A^s}f\!+\!f\left( \frac{|A|}{2}\right) \,|A^s\!\setminus \!A|\\&\ge \int _{A\cap A^s}f+\int _{A\setminus A^s}f=\int _{A}f\,, \end{aligned} \end{aligned}$$

which proves the second part of the result. $\square$

Lemma 9

Let $E\subset \mathbb {R}^2$ be s.t. $0<|E|<\infty$ and ${P(E)<\infty }$. Then, for any $\nu \in \mathbb {S}^1$, denoting $E^s_{\nu }$ the Steiner symmetrization of E with respect to the line through the origin directed by $\nu$, we have

$$\begin{aligned} \frac{\int _{E^s_{\nu }}\eta }{P(E^s_{\nu })}\ge \frac{\int _{E}\eta }{P(E)}\,, \end{aligned}$$

with equality if and only if $|E\triangle E^s_{\nu }|=0$.

Proof

From [27, theorem 14.4], we know that we have ${P(E_{\nu }^s)\le P(E)}$. We now perform a change of coordinates in order to have $E^s_{\nu }=\left\{ (x_1,x_2)\in \mathbb {R}^2\,|\,|x_2|\le \frac{\mathcal {L}^1(E_{x_1})}{2}\right\}$ with

Now, we have

$$\begin{aligned} \begin{aligned} \int _{E}\eta&=\int _{-\infty }^{+\infty }\left( \int _{-\infty }^{+\infty } \eta (x_1,x_2)\,\mathbf {1}_{E}(x_1,x_2)\,\mathrm{d}x_2\right) \mathrm{d}x_1\\&=\int _{-\infty }^{+\infty }\left( \int _{E_{x_1}} \eta (x_1,\cdot )\right) \mathrm{d}x_1\,,\end{aligned} \end{aligned}$$

with $E_{x_1}=\left\{ x_2\in \mathbb {R}\,|\, (x_1,x_2)\in E\right\}$. For almost every ${x_1\in \mathbb {R}}$, we have that ${E_{x_1}}$ is measurable, has finite measure, and that ${\eta (x_1,\cdot )}$ is nonnegative, square integrable, even and decreasing on $\mathbb {R}_+$. We can hence apply Lemma 8 and get that

$$\begin{aligned} \int _{E}\eta \ge \int _{-\infty }^{+\infty }\left( \int _{\left( E_{x_1}\right) ^s} \eta (x_1,\cdot )\right) \mathrm{d}_{x_1}=\int _{E^s_{\nu }}\eta \,. \end{aligned}$$

(38)

Moreover, if $|E\triangle E^s_{\nu }|>0$, then since

$$\begin{aligned} \begin{aligned}&|E\triangle E^s_{\nu }|\\&=\int _{0}^{+\infty }\left( \int _{0}^{+\infty } |\mathbf {1}_E(x_1,x_2)- \mathbf {1}_{E^s_{\nu }}(x_1,x_2)|\,\mathrm{d}x_2\right) \mathrm{d}x_1\\&=\int _{0}^{+\infty }\left( \int _{0}^{+\infty }\left| \mathbf {1}_{E_{x_1}}(x_2)- \mathbf {1}_{\left( E_{x_1}\right) ^s}(x_2)\right| \,\mathrm{d}x_2\right) \mathrm{d}x_1\\&=\int _{0}^{+\infty }\left| E_{x_1}\triangle \left( E_{x_1}^s\right) \right| \,\mathrm{d}x_1\,, \end{aligned} \end{aligned}$$

we get that $\mathcal {L}^1\left( \left\{ x_1\in \mathbb {R}\,|\,\left| E_{x_1} \triangle \left( E_{x_1}\right) ^s\right|>0\right\} \right) >0$ and hence that (38) is strict. $\square$

Lemma 10

Under Assumption 1, the mapping

$$\begin{aligned} \mathcal {G}:R\mapsto \frac{1}{R}\int _{0}^R r\,\tilde{\varphi }(r)\,\mathrm{d}r \end{aligned}$$

has a unique maximizer.

Proof

Since $\varphi$ (and hence $\tilde{\varphi }$) is continuous, we have that $\mathcal {G}$ is $C^1$ on $R_+^*$ and

$$\begin{aligned} \mathcal {G}'(R)=\frac{R\,(R\,\tilde{\varphi }(R))-\int _{0}^R r\,\tilde{\varphi }(r)\,\mathrm{d}r}{R^2}\,. \end{aligned}$$

Now, an integration by part yields that for any continuously differentiable function $h:]0,+\infty [\rightarrow \mathbb {R}$ and for any $x>0$ we have

which shows $H'(x)=x\,h'(x)$. This means the mappings

$$\begin{aligned}&R\mapsto R\,(R\,\tilde{\varphi }(R))\\&-\int _{0}^R r\,\tilde{\varphi }(r)\,\mathrm{d}r \text { and } R\mapsto f(R)=R\,\tilde{\varphi }(R) \end{aligned}$$

have the same variations. Under Assumption 1, it is then easy to show there exists $R_0>0$ such that ${\mathcal {G}'(R_0)=0}$, $\mathcal {G}'$ is positive on $]0,R_0[$ and negative on $]R_0,+\infty [$, hence the result. $\square$

1.3 F.3 Proof of Proposition 12

We define

so that in polar coordinates an equation of the boundary of a regular n-gon of radius R with a vertex at (0, 0) is given by ${r(\theta )=R_n(\theta )}$. Under Assumption 1, we have, for all $R>0$:

$$\begin{aligned} \begin{aligned}&2\pi R\,\frac{\tan \left( \pi /n\right) }{\pi /n}\left| \mathcal {G}(R)- \mathcal {G}_n(R)\right| \\&\quad =\bigg |\frac{\tan \left( \pi /n\right) }{\pi /n}\,\int _{0}^{2\pi }\int _{0}^R r\tilde{\varphi }(r)\,\mathrm{d}r\, \mathrm{d}\theta \\&\qquad \qquad \quad -\int _{0}^{2\pi }\int _{0}^{R_n(\theta )} r\tilde{\varphi }(r)\,\mathrm{d}r\, \mathrm{d}\theta \bigg |\\&\quad =\bigg |\int _{0}^{2\pi }\int _{R_n(\theta )}^R r\tilde{\varphi }(r)\,\mathrm{d}r\, \mathrm{d}\theta \\&\qquad -\left( 1-\frac{\tan \left( \pi /n\right) }{\pi /n}\right) \int _{0}^{2\pi }\int _{0}^{R} r\tilde{\varphi }(r)\,\mathrm{d}r\, \mathrm{d}\theta \bigg |\\&\quad \le \bigg [2\pi \,\underset{\theta \in [0,2\pi ]}{\sup }\left| R- R_n(\theta )\right| \Vert f\Vert _{\infty }\\&\qquad +\left( 1-\frac{\tan \left( \pi /n\right) }{\pi /n}\right) \,2\pi R\,\Vert f\Vert _{\infty }\bigg ]\\&\quad \le \Vert f\Vert _{\infty }\left[ (1- \cos \left( \pi /n\right) ) +\left( 1-\frac{\tan \left( \pi /n\right) }{\pi /n}\right) \right] . \end{aligned} \end{aligned}$$

We hence obtain that $\left| \mathcal {G}(R)-\mathcal {G}_n(R)\right| _{\infty } =O\left( \frac{1}{n^2}\right)$.

Now, assuming f is of class $C^2$ and $f''(\rho _0)<0$ we want to prove that for n large enough, $\mathcal {G}_n$ has a unique maximizer $R^*_n$ and ${|R^*_n-R^*|=O\left( \frac{1}{n}\right) }$. Denoting , we have:

$$\begin{aligned} \begin{aligned} \mathcal {G}_n(R)&=\frac{1}{2\pi R\,\frac{\tan \left( \pi /n\right) }{\pi /n}} \int _{0}^{2\pi }\int _{0}^{R_n(\theta )}r\tilde{\varphi }(r)\,\mathrm{d}r\,\mathrm{d}\theta \\&=\frac{1}{2\pi R\,\frac{\tan \left( \pi /n\right) }{\pi /n}}~n\int _{0}^{2\pi /n} \int _{0}^{R\frac{\cos \left( \pi /n\right) }{\cos \left( \theta -\pi / n\right) }}r\tilde{\varphi }(r)\,\mathrm{d}r\,\mathrm{d}\theta \\&=\frac{\pi /n}{R\,\tan \left( \pi /n\right) }~\int _{0}^{1} \int _{0}^{R\,\alpha _n(s)}r\tilde{\varphi }(r)\,\mathrm{d}r\,\mathrm{d}s\\&=\frac{\pi /n}{\tan \left( \pi /n\right) }\frac{1}{R}\int _{0}^{R} r\left[ \int _{0}^{1}\alpha _n(s)^2\,\tilde{\varphi }(r\,\alpha _n(s))\,\mathrm{d}s\right] \mathrm{d}r\,. \end{aligned} \end{aligned}$$

Considering Lemma 10 and defining

$$\begin{aligned} f_n:r\mapsto r\left[ \int _{0}^{1}\alpha _n(s)^2\,\tilde{\varphi }(r\,\alpha _n(s))\,\mathrm{d}s\right] , \end{aligned}$$

we see that showing $f_n'$ is positive on $]0,\rho _1[$ and negative on ${]\rho _1,+\infty [}$ for some $\rho _1$ is sufficient to prove $\mathcal {G}_n$ has a unique maximizer. Now, we have

$$\begin{aligned} f_n'(r)=\int _{0}^1 \alpha _n(s)^2\left( \tilde{\varphi }(r\,\alpha _n(s))+r\, \alpha _n(s)\,\tilde{\varphi }'(r\,\alpha _n(s))\right) \mathrm{d}s\,. \end{aligned}$$

The image of [0, 1] by $s\mapsto r\,\alpha _n(s)$ is $[r\cos \left( \pi /n\right) ,r]$. Since the mapping $r\mapsto \tilde{\varphi }(r)+r\tilde{\varphi }'(r)=(r\tilde{\varphi })'(r)$ is positive on ${]0,\rho _0[}$ and negative on $]\rho _0,+\infty [$, we get that $f_n'$ is positive on ${]0,\rho _0[}$ and negative on ${]\rho _0/\cos \left( \pi /n\right) ,+\infty [}$ and it hence remains to investigate its sign on ${[\rho _0,\rho _0/\cos \left( \pi /n\right) ]}$. But since f is of class $C^2$ and  ${f''(\rho _0)<0}$ there exists $\epsilon >0$ s.t. ${f''(r)<0}$ on ${]\rho _0-\epsilon ,\rho _0+\epsilon [}$. For n large enough, we hence have

$$\begin{aligned} {[}\rho _0\cos \left( \pi /n\right) ,\rho _0/\cos \left( \pi /n\right) ] \subset \,]\rho _0-\epsilon ,\rho _0+\epsilon [\,, \end{aligned}$$

which implies that

$$\begin{aligned} \forall r\in [\rho _0,\rho _0/\cos \left( \pi /n\right) ],~ r\,\alpha _n(s)\in \,]\rho _0-\epsilon ,\rho _0+\epsilon [\,, \end{aligned}$$

and hence $f_n''(r)<0$. This finally shows there exists $\rho _1$ such that $f_n'$ is positive on $]0,\rho _1[$ and negative on $]\rho _1,+\infty [$, and the result follows as in the proof of Lemma 10.

Now, $R^*$ and $R_n^*$ and are, respectively, the unique solutions of $F(0,R)=0$ and $F(\pi /n,R)=0$ with

One can then show $\frac{\partial }{\partial R}F(0,R)=0$ if and only if $f_0'(R)=0$, i.e. if and only if $R=\rho _0$. But from the proof of Lemma 10 and the above, it is easy to see neither $R^*$ nor $R_n^*$ equals $\rho _0$. We can hence apply the implicit function theorem to finally get that $|R^*-R_n^*|=O\left( \frac{1}{n^2}\right)$.

1.4 F.4 Proof of Proposition 13

1.4.1 F.4.1 Triangles

Let T be a triangle. Up to a rotation of the axis, we can assume that there exist ${a<b}$ and two affine functions u, v such that $v\ge u$ and $u(a)=v(a)$ with

$$\begin{aligned} T=\{(x,y)\in \mathbb {R}^2\,\big |\, x\in [a,b],~u(x)\le y\le v(x)\}\,. \end{aligned}$$

The Steiner symmetrization $T_s$ of T with respect to the line through the origin perpendicular to the side $\{b\}\times [u(b),v(b)]$ is hence obtained by replacing u and v in the definition of T by $(u-v)/2$ and $(v-u)/2$. For all $\theta \in [0,1]$, we define

and

so that $T_{1/2}=T_s$. Let us now show that

$$\begin{aligned} \frac{\mathrm{d}}{\mathrm{d}\theta }\mathcal {J}\,(T_{\theta })\big |_{\theta =0}\le 0\,, \end{aligned}$$

with equality if and only if T is symmetric with respect to the symmetrization line.

Weighted area term: first, we have:

$$\begin{aligned} \int _{T_{\theta }}\eta =\int _{a}^b \left( \int _{u_{\theta }(x)}^{v_{\theta }(x)} \eta \left( \sqrt{x^2+y^2}\right) \mathrm{d}y\right) \mathrm{d}x\,. \end{aligned}$$

Hence,

$$\begin{aligned}&\frac{\mathrm{d}}{\mathrm{d}\theta }\int _{T_{\theta }}\eta \bigg |_{\theta =0}=\\&-\int _{a}^b(u+v)(x)\,(g_x(|v|(x))-g_x(|u|(x)))\,\mathrm{d}x\,, \end{aligned}$$

with . Our assumptions on $\eta$ ensure that ${p\mapsto g_x(p)}$ is decreasing, so that $g_x(|v|(x))-g_x(|u|(x))$ and $|u|(x)-|v|(x)$ have the same sign. But since

$$\begin{aligned} -(u(x)+v(x)) ~\text { and }~ -(|u|(x)-|v|(x)) \end{aligned}$$

also have the same sign, we have that

$$\begin{aligned} -(u+v)(x)\,(g_x(|v|(x))-g_x(|u|(x)))<0\,, \end{aligned}$$

unless $u(x)=v(x)$ or $u(x)=-v(x)$. Since u and v are affine and $u(a)=v(a)$, the first equality cannot hold for any ${x\in ]a,b[}$ (otherwise, we would have $u=v$ on [a, b] and T would be flat). Moreover, ${u(x)=-v(x)}$ almost everywhere on [a, b] if and only if $T=T_s$. Hence, $\frac{\mathrm{d}}{\mathrm{d}\theta }\int _{T_{\theta }}\eta \big |_{\theta =0}\le 0$ with equality if and only if $T=T_s$.

Perimeter term: now, the perimeter of $T_{\theta }$ is given by

$$\begin{aligned} \begin{aligned} P(T_{\theta })&=\int _{a}^b \sqrt{1+|\nabla u_{\theta }|^2}+\int _{a}^b \sqrt{1+|\nabla v_{\theta }|^2}+v_{\theta }(b)-u_{\theta }(b)\\&=(b-a)\left( f(\nabla u_{\theta })+f(\nabla v_{\theta })\right) +(v(b)-u(b))\,, \end{aligned} \end{aligned}$$

with , this last function being strictly convex. Now, since

$$\begin{aligned} \left\{ \begin{aligned} \nabla u_{\theta }&=\nabla u-\theta (\nabla u+\nabla v)\,,\\ \nabla v_{\theta }&=\nabla v-\theta (\nabla u+\nabla v)\,, \end{aligned}\right. \end{aligned}$$

we get

$$\begin{aligned} \begin{aligned}&\frac{\mathrm{d}}{\mathrm{d}\theta }P(T_{\theta })\bigg |_{\theta =0}=(b-a) \left[ \nabla f(\nabla u)+\nabla f(\nabla v)\right] \cdot \left[ -(\nabla u+\nabla v)\right] \\&\qquad \qquad ~=-(b-a)\left[ \nabla f(\nabla u)- \nabla f(-\nabla v)\right] \cdot \left[ \nabla u-(-\nabla v)\right] , \end{aligned} \end{aligned}$$

and the strict convexity of f hence shows

$$\begin{aligned} \frac{\mathrm{d}}{\mathrm{d}\theta }P(T_{\theta })\bigg |_{\theta =0}\le 0\,, \end{aligned}$$

with equality if and only if $\nabla u=-\nabla v$, which means, up to a translation, that T is equal to $T_s$.

Applying the above arguments to all three sides finally yields the result.

1.4.2 F.4.2 Quadrilaterals

Let Q be a simple quadrilateral. Up to a rotation of the axis, we can assume that there exist ${a<b<c}$ and four affine functions $u_1,v_1,u_2,v_2$ such that

$$\begin{aligned} \left\{ \begin{aligned} v_1\ge u_1,&~v_2\ge u_2\,,\\ u_1(a)=v_1(a),&~u_2(c)=v_2(c)\,,\\ u_1(b)=u_2(b),&~v_1(b)=v_2(b)\,, \end{aligned}\right. \end{aligned}$$

with $Q=T_1\cup T_2$ and

For all $\theta \in [0,1]$ and $i\in \{1,2\}$, we define

and $Q_{\theta }=T_{1,\theta }\cup T_{2,\theta }$ with

$$\begin{aligned} T_{i,\theta }=\left\{ (x,y)\in \mathbb {R}^2\,\big |\, x\in [a,b],~u_{i,\theta }(x)\le y\le v_{i,\theta }(x)\right\} , \end{aligned}$$

so that the Steiner symmetrization $Q^s$ of Q with respect to the ligne through the origin perpendicular to the diagonal ${\{b\}\times [u_1(b),v_1(b)]}$ satisfies $Q_{1/2}=Q^s$.

Weighted area term: the fact $\frac{\mathrm{d}}{\mathrm{d}\theta }\int _{Q_{\theta }}\eta \big |_{\theta =0}\le 0$ with equality if and only if $Q=Q^s$ can easily be deduced from the case of triangles using the fact that $\int _{Q_{\theta }}\eta =\int _{T_{1,\theta }}\eta +\int _{T_{2,\theta }}\eta$.

Perimeter term: now, the perimeter of $Q_{\theta }$ is given by:

$$\begin{aligned} \begin{aligned} P(Q_{\theta })&=\int _{a}^b \sqrt{1+|\nabla u_{1,\theta }|^2}+\int _{a}^b \sqrt{1+|\nabla v_{1,\theta }|^2}\\&+\int _{b}^c \sqrt{1+|\nabla u_{2,\theta }|^2}+\int _{b}^c \sqrt{1+|\nabla v_{2,\theta }|^2}\\&=(b-a)\left( f(\nabla u_{1,\theta })+f(\nabla v_{1,\theta })\right) \\ {}&+(c-b)\left( f(\nabla u_{2,\theta })+f(\nabla v_{2,\theta })\right) \end{aligned} \end{aligned}$$

with as before. We then get

$$\begin{aligned} \begin{aligned}&\frac{\mathrm{d}}{\mathrm{d}\theta }P(Q_{\theta })\bigg |_{\theta =0}\\ =&-(b-a)\left[ \nabla f(\nabla u_1)-\nabla f(-\nabla v_1)\right] \cdot \left[ \nabla u_1-(-\nabla v_1)\right] \\&-(c-b)\left[ \nabla f(\nabla u_2)-\nabla f(-\nabla v_2)\right] \cdot \left[ \nabla u_2-(-\nabla v_2)\right] , \end{aligned} \end{aligned}$$

and the strict convexity of f hence shows

$$\begin{aligned} \frac{\mathrm{d}}{\mathrm{d}\theta }P(Q_{\theta })\bigg |_{\theta =0}\le 0\,, \end{aligned}$$

with equality if and only if $\nabla u_1=-\nabla v_1$ and $\nabla u_2=-\nabla v_2$, which means, up to a translation, that Q is equal to $Q^s$.