Cheeger sets and clusters, optimal packing

A $\Gamma$- convergence method for the study of Cheeger sets and Optimal Packings

Collaboration with Dorin Bucur and Ilaria Fragala.

As you can see in some previous posts (link1, link2) it is possible to approximate the perimeter using a $\Gamma$-convergence result of the Modica-Mortola type (see link1 above). This motivated us to search a similar formulation for the Cheeger set. Recall that the Cheeger set associated to a set $D$ is the set $\omega$ which is included in $D$ and which minimizes the ratio perimeter/volume: $|\partial \omega|/|\omega$.

The fact that we minimize a term containing the perimeter already suggests the use of the Modica-Mortola approximation for the perimeter term. You may think that the area term should not pose any problem since an integral representation should do. However, since we divide by the volume term, it turns out that the $L^1$ norm is not enough to assure us that we do not have degeneracies and a higher order norm needs to be applied for things to work.

The details can be found in the following article file. I simply state the Gamma convergence result used in the numerics below.

For any fixed $\alpha > \frac{N-1}{N} $ and $p>1$, the functional $$F(\Omega_1, \dots, \Omega_k):= \sum_{i=1}^k \Big (\frac{{\mathcal H}^{N-1}(\partial^* \Omega_i)}{|\Omega_i|^\alpha} \Big ) ^p $$ is the $\Gamma$-limit as $\varepsilon \to 0$ in $L^1(D, \Bbb{R}^N)$ of the sequence $$ F_\varepsilon (u_1, \dots, u_k):= \sum_{i=1}^k \Big ( \frac{\varepsilon \int_D|\nabla u_i|^2 dx+ \frac{9} {\varepsilon}\int _D u_i^2 (1-u_i)^2}{\Big (\int_D |u_i|^\frac{2N}{N-1}dx \Big )^\alpha} \Big ) ^ p+ \frac 1\varepsilon \sum_{1 \le i < j \le k} \int_D u_i^2u_j^2dx $$ if $u_i \in H_0^1(D)$, $0\leq u_i \leq 1$ and $+\infty$ if not

We use a $p$-norm to be able to cover the sum minimization for $p=1$, as well as the minimization of the maximal Cheeger constant, for $p$ large. We choose to work with a penalized non-overlapping constraint which avoids some local minima consisting of constant densities.

A finite element variant of the algorithm can be found at: https://github.com/bbogo/Cheeger_patch. Together with this there is also an implementation of the Kawohl, Lachand-Robert algorithm for finding Cheeger sets for convex polygons using the very efficient Clipper toolbox. It can work with polygons with hundreds of vertices, so general convex sets can also be treated with no problem if you can obtain a polygonal approximation.

I start by showing the efficiency of the algorithm in computing the Cheeger set for a convex domain in the plane. In general when plotting the result using the $\Gamma$-convergence method and the one using the Kawohl, Lachand-Robert method, they are indistinguishable and the relative error between corresponding Cheeger constants is really low.


Cheeger set in equilateral triangle	Cheeger set in square	General Cheeger set	Kawohl, Lachand-Robert algorithm - Reuleaux triangle. Approximation with a polygon with 402 vertices.

Generalization of the algorithm to multiple cells is straightforward. We can also go in 3D with no additional problem (aside slightly longer computational time)