# Asymptotic optimality of the triangular lattice for a class of optimal
location problems

David P. Bourne, Riccardo Cristoferi  Maxwell Institute for Mathematical
Sciences and Department of Mathematics, Heriot-Watt University, UK
<EMAIL_ADDRESS>Radboud University
Department of Mathematics
Nijmegen
Netherlands<EMAIL_ADDRESS>
###### Abstract.

We prove an asymptotic crystallization result in two dimensions for a class of
nonlocal particle systems. To be precise, we consider the best approximation
with respect to the 2-Wasserstein metric of a given absolutely continuous
probability measure $f\mathrm{d}x$ by a discrete probability measure
$\sum_{i}m_{i}\delta_{z_{i}}$, subject to a constraint on the particle sizes
$m_{i}$. The locations $z_{i}$ of the particles, their sizes $m_{i}$, and the
number of particles are all unknowns of the problem. We study a one-parameter
family of constraints. This is an example of an optimal location problem (or
an optimal sampling or quantization problem) and it has applications in
economics, signal compression, and numerical integration. We establish the
asymptotic minimum value of the (rescaled) approximation error as the number
of particles goes to infinity. In particular, we show that for the constrained
best approximation of the Lebesgue measure by a discrete measure, the discrete
measure whose support is a triangular lattice is asymptotically optimal. In
addition, we prove an analogous result for a problem where the constraint is
replaced by a penalization. These results can also be viewed as the asymptotic
optimality of the hexagonal tiling for an optimal partitioning problem. They
generalise the crystallization result of Bourne, Peletier and Theil
(Communications in Mathematical Physics, 2014) from a single particle system
to a class of particle systems, and prove a case of a conjecture by Bouchitté,
Jimenez and Mahadevan (Journal de Mathématiques Pures et Appliquées, 2011).
Finally, we prove a crystallization result which states that optimal
configurations with energy close to that of a triangular lattice are
geometrically close to a triangular lattice.

###### Key words and phrases:

crystallization, quantization, optimal partition, optimal sampling, Honeycomb
conjecture, semi-discrete optimal transport

##  1\. Introduction

Consider the problem of approximating an absolutely continuous probability
measure by a discrete probability measure. To quantify the quality of the
approximation, we measure the approximation error in the 2-Wasserstein metric.
Let $\Omega\subset\mathbb{R}^{d}$ be the closure of an open and bounded set,
and let

$f\in L^{1}(\Omega),\quad\quad f\geq
c>0,\quad\quad\int_{\Omega}f(x)\,\mathrm{d}x=1,$ (1)

be the density of the absolutely continuous probability measure. We
approximate $f\mathrm{d}x$ by a discrete measure from the set

$\mathcal{P}_{\mathrm{d}}(\Omega):=\left\\{\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}:N_{\mu}\in\mathbb{N},\,m_{i}>0,\,\sum_{i=1}^{N_{\mu}}m_{i}=1,\,z_{i}\in\Omega,\,z_{i}\neq
z_{j}\textrm{ if }i\neq j\right\\}.$

For $\mu\in\mathcal{P}_{\mathrm{d}}(\Omega)$, we define
$N_{\mu}:=\\#\mathrm{supp}(\mu)$, which is not fixed a priori. For $p\geq 1$,
the $p$-Wasserstein distance (see [65, 71]) between $f\mathrm{d}x$ and
$\mu\in\mathcal{P}_{\mathrm{d}}(\Omega)$ is

$W_{p}(f,\mu)\>=\\\
\inf\left\\{\int_{\Omega}|x-T(x)|^{p}f(x)\,\mathrm{d}x\,:\,T:\Omega\to\\{z_{i}\\}_{i=1}^{N_{\mu}}\text{
is
Borel},\,\int_{T^{-1}(\\{z_{i}\\})}f(x)\,\mathrm{d}x=m_{i}\,\,\forall\,i\right\\}^{\frac{1}{p}}.$
(2)

Observe that

$\inf\\{W_{p}(f,\mu):\mu\in\mathcal{P}_{\mathrm{d}}(\Omega)\\}=0$

since there exists a sequence of discrete measures $\mu_{n}$ converging
weakly∗ to $f\mathrm{d}x$, with $N_{\mu_{n}}\to\infty$ as $n\to\infty$. On the
other hand, for each $N\in\mathbb{N}$,
$\inf\\{W_{p}(f,\mu):\mu\in\mathcal{P}_{\mathrm{d}}(\Omega),\,N_{\mu}\leq
N\\}>0$. Therefore the problem
$\inf\\{W_{p}(f,\mu):\mu\in\mathcal{P}_{\mathrm{d}}(\Omega)\\}$ has no
solution. To obtain a minimizer we must constrain the number of atoms
$N_{\mu}$, either explicitly (with a constraint) or implicitly (with a
penalization). Given an _entropy_
$H:\mathcal{P}_{\mathrm{d}}(\Omega)\to[0,\infty]$ (defined below) we consider
the _constrained_ optimal location problem

$\inf\left\\{W^{p}_{p}(f,\mu):\mu\in\mathcal{P}_{\mathrm{d}}(\Omega),\,H(\mu)\leq
L\right\\}=:\mathcal{E}^{p,d}_{H}(L),$ (3)

where $L>0$, and the _penalized_ optimal location problem

$\inf\left\\{W^{p}_{p}(f,\mu)+\delta
H(\mu):\mu\in\mathcal{P}_{\mathrm{d}}(\Omega)\right\\}=:\mathcal{F}^{p,d}_{H}(\delta),$
(4)

where $\delta>0$. If $H$ satisfies $H(\mu)\to\infty$ as $N_{\mu}\to\infty$,
then minimising sequences for problems (3) and (4) have a uniformly bounded
number of atoms. If in addition $H$ is lower semi-continuous with respect to
the weak∗ convergence of measures, then problems (3) and (4) admit a solution.

When $L$ or $\delta$ are fixed, the geometry of the set $\Omega$ has a strong
effect on optimal particle arrangements, and it is very difficult to
characterise minimising configurations. As $L$ increases, or $\delta$
decreases, the optimal number of particles $N_{\mu}$ increases, and it is
believed that optimal configurations locally form regular, periodic patterns;
see the numerical evidence in Figures 1 and 2. This phenomenon is known as
_crystallization_ (see Section 1.3 for more on this). The specific geometry of
these patterns depends on the choice of $p$ in the Wasserstein distance, the
choice of $H$, and the dimension $d$. In this paper we will study the
crystallization problem by taking the limits $L\to\infty$ and $\delta\to 0$.

(a) $\alpha=0.1$, $\delta=2.243\times 10^{-3}$

(b) $\alpha=0.1$, $\delta=1.303\times 10^{-4}$

(c) $\alpha=0.1$, $\delta=7.567\times 10^{-6}$

(d) $\alpha=0.583$, $\delta=1.472\times 10^{-2}$

(e) $\alpha=0.583$, $\delta=1.763\times 10^{-3}$

(f) $\alpha=0.583$, $\delta=2.111\times 10^{-4}$

(g) $\alpha=0.9$, $\delta=1.274\times 10^{-1}$

(h) $\alpha=0.9$, $\delta=2.452\times 10^{-2}$

(i) $\alpha=0.9$, $\delta=4.721\times 10^{-3}$

Figure 1. Approximate local minimizers for the penalized problem (4) for the
case $p=d=2$, $\Omega=[0,1]^{2}$, $f=\mathbbm{1}_{\Omega}$,
$H_{\alpha}(\mu)=\sum_{i}m_{i}^{\alpha}$, for several values of $\alpha$ and
$\delta$. The value of $\alpha$ is constant in each row, and the value of
$\delta$ decreases from left to right in each row. The black dots are the
particles $z_{i}$, where $\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}$ is an
approximate local minimizer of (4). The polygons are the sets
$T^{-1}(\\{z_{i}\\})$, where $T$ is the optimal transport map in (2). The
particles $z_{i}$ are located at the centroids of the polygons. The masses
$m_{i}$ are the areas of the polygons. The colours correspond to the number of
sides: squares are yellow, pentagons are orange, hexagons are blue, and
heptagons are red. For each value of $\alpha$, a hexagonal tiling (with
defects) starts to emerge as $\delta$ is decreased. This figure, Figure 2 and
Table 1 were made by Steven Roper using the generalized Lloyd algorithm from
[19]. To search for a global minimizer in the highly non-convex energy
landscape, the algorithm was ran many times using different, randomly
generated initial conditions. The values of $\delta$ were chosen by first
choosing a target value of $N_{\mu}$ and then using the heuristic (16) to
generate the corresponding $\delta$. Better results, without defects, can be
achieved by taking the initial particle locations to be a perturbation of a
triangular lattice; see Figure 2.

(a) $\alpha=0.583$, $\delta=1.763\times 10^{-3}$

(b) $\alpha=0.583$, $\delta=2.111\times 10^{-4}$

Figure 2. Approximate global minimizers for the penalized problem (4) for the
case $p=d=2$, $\Omega=[0,1]^{2}$, $f=\mathbbm{1}_{\Omega}$,
$H_{\alpha}(\mu)=\sum_{i}m_{i}^{\alpha}$, $\alpha=0.583$ for the values of
$\delta$ used in Figure 2 (middle row, middle and right columns). See the
caption to Figure 1 for a description of the polygons and the colour scheme.
These configurations have lower energy ($W_{2}^{2}(f,\mu)+\delta
H_{\alpha}(\mu)$) than the corresponding configurations shown in Figure 1, and
they do not have defects. This figure was generated by Steven Roper using the
generalized Lloyd algorithm from [19] and by taking the initial conditions to
be perturbations of a triangular lattice. In Figure 1 (middle row, right
column) there are $N_{\mu}=200$ particles whereas in this figure (right) there
are $N_{\mu}=202$ particles; algorithm [19] attempts to find the optimum
number of particles.

For the entropy

$H(\mu)=\\#\mathrm{supp}(\mu)$ (5)

Zador’s Theorem for the asymptotic quantization error states that

$\lim_{L\to\infty}\left[L^{\frac{p}{d}}\mathcal{E}^{p,d}_{H}(L)\right]=C_{p,d}\left(\int_{\Omega}f(x)^{\frac{d}{d+p}}\,\mathrm{d}x\right)^{\frac{d+p}{d}}$
(6)

for some positive constant $C_{p,d}$ that is independent of the density $f$.
See for example [20, 41, 45, 74] and see [44, 51, 53] for the more general
case where $\Omega$ is a Riemannian manifold. The constant $C_{p,d}$ is known
in two dimensions:

$C_{p,2}=\int_{P_{6}}|x|^{p}\,\mathrm{d}x,$ (7)

where $P_{6}$ is a regular hexagon of unit area centred at the origin. This
follows from Fejes Tóth’s Theorem on Sums of Moments (see [37, 43]), which has
also been proved in various levels of generality by several other authors
including [13, 36, 59, 61].

The geometric interpretation of (6) and (7) is the following: In two
dimensions it is asymptotically optimal to arrange the atoms of the discrete
measure at the centres of regular hexagons, i.e., on a regular triangular
lattice, where the areas of the hexagons depend on the density $f$. Locally,
where $f$ is approximately constant, these hexagons form a regular honeycomb.
By the _regular triangular lattice_ we mean the set
$\mathbb{Z}(1,0)\oplus\mathbb{Z}(1/2,\sqrt{3}/2)$ up to dilation and isometry.
See Remark 1.3 below for more on this geometric interpretation.

Formula (6) was extended to more general entropies by Bouchitté, Jimenez and
Mahadevan in [14]. Their class of entropies includes the case

$H_{\alpha}(\mu)=\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha},$ (8)

where $\alpha\in(-\infty,1)$. This reduces to the entropy (5) when $\alpha=0$.
Bouchitté, Jimenez and Mahadevan [14, Proposition 3.11(i)] proved that

$\lim_{L\to\infty}\left[L^{\frac{p}{d(1-\alpha)}}\mathcal{E}^{p,d}_{H_{\alpha}}(L)\right]=C_{p,d}(\alpha)\left(\int_{\Omega}f(x)^{\frac{d(1-\alpha)+\alpha
p}{d(1-\alpha)+p}}\,\mathrm{d}x\right)^{1+\frac{p}{d(1-\alpha)}}$ (9)

for some positive constant $C_{p,d}(\alpha)$. Moreover, they conjectured [14,
Section 3.6 (ii)] that

$C_{p,d}(\alpha)\textrm{ is independent of }\alpha.$

If this conjecture is true, then by (7)

$C_{p,2}(\alpha)=C_{p,2}(0)=\int_{P_{6}}|x|^{p}\,\mathrm{d}x.$

In particular, the conjecture for the case $p=2$, $d=2$ is

$C_{2,2}(\alpha)=\int_{P_{6}}|x|^{2}\,\mathrm{d}x=\frac{5}{18\sqrt{3}}=:c_{6}$
(10)

for all $\alpha\in(-\infty,1)$. It is known that $C_{2,2}(\alpha)=c_{6}$ for
all $\alpha\in(-\infty,0]$ (see [14, Section 3.6]) and so it remains to
establish the conjecture for the case $\alpha\in(0,1)$. The conjecture would
mean that in two dimensions a discrete measure supported on a regular
triangular lattice gives asymptotically the best constrained approximation of
the Lebesgue measure (again, see Remark 1.3 below for this geometric
interpretation).

###  1.1. Main results

In this paper we prove conjecture (10) for all
$\alpha\in(-\infty,\overline{\alpha}]$, where $\overline{\alpha}=0.583$; see
Theorem 1.2. The conjecture for $\alpha\in(\overline{\alpha},1)$ remains open,
although we suggest a direction for proving it in Theorem 6.1, where we prove
it under an additional assumption. In Theorem 1.1 we prove an analogous
asymptotic quantization formula for the penalized optimal location problem (4)
for all $\alpha\in(-\infty,\overline{\alpha}]$. This generalises the
crystallization result of [18], where Theorem 1.1 was proved for the special
case $\alpha=0.5$, $f=1$.  Moreover, for the case $f=1$, we prove that minimal
configurations are ‘asymptotically approximately’ a triangular lattice; see
Theorem 1.4. To be more precise, we prove that, as $\delta\to 0$, rescaled
minimal configurations for the penalized quantization problem are
quantitatively close to a triangular lattice. This result will be proved for
the case $\alpha=\overline{\alpha}$. The proof can be easily modified for any
$\alpha\leq\overline{\alpha}$.

Define the constrained optimal quantization error by

$\mathrm{m_{c}}(\alpha,L):=\mathcal{E}^{2,2}_{H_{\alpha}}(L)=\inf\left\\{W^{2}_{2}(f,\mu):\mu\in\mathcal{P}_{\mathrm{d}}(\Omega),\,\,\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}\leq
L\right\\},$ (11)

and the penalized optimal quantization error by

$\mathrm{m_{p}}(\alpha,\delta):=\mathcal{F}^{2,2}_{H_{\alpha}}(\delta)=\inf\left\\{W^{2}_{2}\left(\,f,\mu\,\right)+\delta\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}:\mu\in\mathcal{P}_{\mathrm{d}}(\Omega)\right\\}.$
(12)

Since the Wasserstein distance on the compact set $\Omega$ metrizes the tight
convergence of probability measures, and the map
$\mu\mapsto\sum_{i}m_{i}^{\alpha}$ is lower semi-continuous with respect to
this convergence [65, Lemma 7.11], both infima above are attained. Our main
results are the following.

######  Theorem 1.1 (Asymptotic crystallization for the penalized optimal
location problem).

Let  $\alpha\in(-\infty,\overline{\alpha}]$, where $\overline{\alpha}:=0.583$.
Let $\Omega\subset\mathbb{R}^{2}$ be the closure of an open and bounded set.
Assume that $f:\Omega\to[0,\infty)$ is lower semi-continuous with $f\geq c>0$
and $\int_{\Omega}f\,\mathrm{d}x=1$. Then

$\lim_{\delta\to
0}\left[\left(\frac{c_{6}}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}}\mathrm{m_{p}}(\alpha,\delta)\right]=\frac{2-\alpha}{1-\alpha}\,c_{6}\int_{\Omega}f(x)^{\frac{1}{2-\alpha}}\,\mathrm{d}x.$
(13)

Taking the special case $f=1$, $|\Omega|=1$, $\alpha=0.5$ in Theorem 1.1 gives
[18, Theorem 2]. We illustrate Theorem 1.1 in Table 1 and Figures 1 and 2.

######  Theorem 1.2 (Asymptotic crystallization for the constrained optimal
location problem).

Let  $\alpha\in(-\infty,\overline{\alpha}]$, where $\overline{\alpha}:=0.583$.
Let $\Omega\subset\mathbb{R}^{2}$ be the closure of an open and bounded set.
Assume that $f:\Omega\to[0,\infty)$ is lower semi-continuous with $f\geq c>0$
and $\int_{\Omega}f\,\mathrm{d}x=1$. Then

$\lim_{L\to\infty}\left[L^{\frac{1}{1-\alpha}}\,\mathrm{m_{c}}(\alpha,L)\right]=c_{6}\left(\int_{\Omega}f(x)^{\frac{1}{2-\alpha}}\,\mathrm{d}x\right)^{\frac{2-\alpha}{1-\alpha}}.$
(14)

By comparing equation (9) to equation (14) with $p=d=2$, we read off that
$C_{2,2}(\alpha)=c_{6}$ for all  $\alpha\in(-\infty,\overline{\alpha}]$, which
proves conjecture (10) for this range of $\alpha$. We believe that Theorem 1.1
and Theorem 1.2 hold for all  $\alpha\in(-\infty,1)$, not just for
$\alpha\in(-\infty,\overline{\alpha}]$, but we are only able to prove them for
the whole range of $\alpha$ if we make an ansatz about minimal configurations;
see Theorem 6.1.

$\,\;\alpha\;\,$ | $\,\;\delta\;\,$ | $\,\;\frac{\left(\frac{c_{6}}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}\phantom{\big{|}}}\\!\\!\\!\left(W_{2}^{2}(\mathbbm{1}_{\Omega},\mu)+\delta H_{\alpha}(\mu)\right)}{c_{6}(2-\alpha)/(1-\alpha)}\,\;$
---|---|---
0.1 | 0.0022433361900 | 1.025664680453751
0.1 | 0.0001302910000 | 1.012634927464421
0.1 | $7.5672376050508\times 10^{-6}$ | 1.006166789745220
0.583 | 0.0147231527000 | 1.015173622346968
0.583 | 0.0017628730000 | 1.007372522192174
0.583 | $2.1107719443098\times 10^{-4}$ | 1.003575800389361
0.9 | 0.1273904500000 | 1.004506412114665
0.9 | 0.0245228180000 | 1.002133746895388
0.9 | 0.004720672550584 | 1.001028468127525
Table 1. Illustration of Theorem 1.1 for the case $\Omega=[0,1]^{2}$,
$f=\mathbbm{1}_{\Omega}$. In the last column we give the ratio of a numerical
approximation of
$\big{(}\tfrac{c_{6}}{\delta(1-\alpha)}\big{)}^{\frac{1}{2-\alpha}}\mathrm{m_{p}}(\alpha,\delta)$
(which appears on the left-hand side of (13)) to
$\frac{2-\alpha}{1-\alpha}\,c_{6}$ (which appears on the right-hand side of
(13); note that $\int_{\Omega}f(x)^{\frac{1}{2-\alpha}}\,\mathrm{d}x=1$ here).
For three representative values of $\alpha$, we see that the ratio tends to
$1$ as $\delta$ tends to $0$, which supports Theorems 1.1 and 6.1. The
numerical approximation of the minimum energy and the choice of $\delta$ is
described in Figures 1 and 2.

######  Remark 1.3 (Energy scaling and the geometric interpretation of
Theorems 1.1 & 1.2).

To motivate the rescaling on the left-hand side of (13) we reason as follows.
Let

$\Omega=\bigcup_{i=1}^{N}H_{i}$

be the union of $N$ disjoint regular hexagons of equal area $|\Omega|/N$. Let
$z_{i}$ be the centroid of $H_{i}$ and let
$f=\tfrac{1}{|\Omega|}\mathbbm{1}_{\Omega}$ be the uniform probability
distribution on $\Omega$. Here $\mathbbm{1}_{\Omega}$ denotes the
characteristic function of the set $\Omega$. By definition of $c_{6}$
(equation (10)) and a change of variables,

$\int_{H_{i}}|x-z_{i}|^{2}\,\mathrm{d}x=c_{6}|H_{i}|^{2}=c_{6}\left(\frac{|\Omega|}{N}\right)^{2}$

for all $i$. Therefore the penalized quantization error of approximating
$f\mathrm{d}x$ by $\mu=\sum_{i=1}^{N}\tfrac{1}{N}\delta_{z_{i}}$ is

$W_{2}^{2}(f,\mu)+\delta
H_{\alpha}(\mu)=\sum_{i=1}^{N}\int_{H_{i}}|x-z_{i}|^{2}\frac{1}{|\Omega|}\,\mathrm{d}x+\delta
N\left(\frac{1}{N}\right)^{\alpha}=c_{6}\frac{|\Omega|}{N}+\delta
N^{1-\alpha}.$ (15)

The right-hand side of (15) is minimized when

$N=\left(\frac{c_{6}|\Omega|}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}}.$
(16)

Substituting this value of $N$ into (15) (assuming for a moment that it is an
integer) gives

$\left(\frac{c_{6}}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}}\left(W_{2}^{2}(f,\mu)+\delta
H_{\alpha}(\mu)\right)=\frac{2-\alpha}{1-\alpha}\,c_{6}\,|\Omega|^{\frac{1-\alpha}{2-\alpha}}=\frac{2-\alpha}{1-\alpha}\,c_{6}\int_{\Omega}f(x)^{\frac{1}{2-\alpha}}\,\mathrm{d}x,$

which motivates the rescaling used in (13). This heuristic computation
suggests an upper bound for the left-hand side of (13), for the case where $f$
is the uniform distribution. Theorem 1.1 says that this upper bound is in fact
asymptotically optimal. In this sense we can say that the honeycomb structure
gives asymptotically the best approximation of the uniform distribution.

The rescaling used in (14) can be derived in a similar way. Indeed, fix $L>0$
and consider the constraint

$H_{\alpha}(\mu)=\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}\leq L.$

If all the masses are the same, $m_{i}=1/N_{\mu}$ for all $i$, then the
biggest number $N_{\mu}$ for which this constraint is satisfied is

$N_{\mu}=L^{\frac{1}{1-\alpha}}.$

Assuming that $N_{\mu}$ is an integer, take as above

$\Omega=\bigcup_{i=1}^{N_{\mu}}H_{i},\quad\quad
f=\frac{1}{|\Omega|}\mathbbm{1}_{\Omega},\quad\quad\mu=\sum_{i=1}^{N_{\mu}}\frac{1}{N_{\mu}}\delta_{z_{i}}.$

Then

$L^{\frac{1}{1-\alpha}}\,W_{2}^{2}(f,\mu)=c_{6}\,|\Omega|=c_{6}\left(\,\int_{\Omega}f(x)^{\frac{1}{2-\alpha}}\,\mathrm{d}x\,\right)^{\frac{2-\alpha}{1-\alpha}},$

which motivates the rescaling used in (14). Combining this formal calculation
with Theorem 1.2 again suggests the asymptotic optimality of the honeycomb.

Theorem 1.1 gives the asymptotic minimum value of the penalized quantization
error but says nothing about the configuration of the particles; it says that
the triangular lattice is asymptotically optimal, but it does not say that
asymptotically optimal configurations are close to a triangular lattice. We
prove this in the following theorem.

######  Theorem 1.4 (Asymptotically optimal configurations are close to a
regular triangular lattice).

Let $\Omega\subset\mathbb{R}^{2}$ be a convex polygon with at most six sides,
$|\Omega|=1$, $f=\mathbbm{1}_{\Omega}$, and $\alpha=\overline{\alpha}$. There
exist constants $\varepsilon_{0},c,\beta_{1},\beta_{2}>0$ with the following
property. Let $\delta>0$ and
$\mu_{\delta}=\sum_{i=1}^{N_{\delta}}\widetilde{m}_{i}\delta_{\widetilde{z}_{i}}\in\mathcal{P}_{\mathrm{d}}(\Omega)$
be a solution of the penalized quantization problem defining
$\mathrm{m}_{\mathrm{p}}(\alpha,\delta)$. Define the defect of $\mu_{\delta}$
by

$\mathrm{d}(\mu_{\delta}):=\left(\frac{c_{6}}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}}\mathrm{m_{p}}(\alpha,\delta)-\frac{2-\alpha}{1-\alpha}\,c_{6}.$

Note that $\lim_{\delta\to 0}\mathrm{d}(\mu_{\delta})=0$ by Theorem 1.1.
Define

$V_{\delta,\alpha}=\left(\frac{c_{6}}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}}.$

Define rescaled particle positions
$z_{i}=V_{\delta,\alpha}^{1/2}\widetilde{z}_{i}$,
$i\in\\{1,\ldots,N_{\delta}\\}$. Let $\\{V_{i}\\}_{i=1}^{N_{\delta}}$ be the
Voronoi tessellation of $\Omega$ generated by
$\\{z_{i}\\}_{i=1}^{N_{\delta}}$, i.e.,

$V_{i}=\\{z\in
V_{\delta,\alpha}^{1/2}\Omega:|z-z_{i}|\leq|z-z_{j}|\;\forall\,j\in\\{1,\ldots,N_{\delta}\\}\\}.$

  * (a)

The optimal number of particles $N_{\delta}$ is asymptotically equal to
$V_{\delta,\alpha}$:

$\lim_{\delta\to 0}\frac{V_{\delta,\alpha}}{N_{\delta}}=1.$

  * (b)

If $\delta>0$ is sufficiently small, and if
$\varepsilon\in(0,\varepsilon_{0})$ and $\mu_{\delta}$ satisfy

$\beta_{1}\mathrm{d}(\mu_{\delta})+\beta_{2}V_{\delta,\alpha}^{-1/2}\leq\varepsilon,$
(17)

then, with the possible exception of at most $N_{\delta}c\varepsilon^{1/3}$
indices $i\in\\{1,\dots,N_{\delta}\\}$, the following hold:

    * (i)

$V_{i}$ is a hexagon;

    * (ii)

the distance between $z_{i}$ and each vertex of $V_{i}$ is between
$(1\pm\varepsilon^{1/3})\sqrt{\frac{V_{\delta,\alpha}}{N_{\delta}}}\sqrt{\frac{\phantom{|}2\phantom{|}}{3\sqrt{3}}}$;

    * (iii)

the distance between $z_{i}$ and each edge of $V_{i}$ is between
$(1\pm\varepsilon^{1/3})\sqrt{\frac{V_{\delta,\alpha}}{N_{\delta}}}\sqrt{\frac{\phantom{|}1\phantom{|}}{2\sqrt{3}}}$.

Even though Theorem 1.4 is stated only for the case
$\alpha=\overline{\alpha}$, the same proof holds for any
$\alpha\leq\overline{\alpha}$, up to proving the convexity inequality (25) for
that specific value of $\alpha$ (by using the same strategy we used for the
case $\alpha=\overline{\alpha}$). A similar result can be proved for the
constrained quantization problem.

######  Remark 1.5 (Geometric interpretation of Theorem 1.4).

Note that the term $\beta_{2}V_{\delta,\alpha}^{-1/2}$ in (17) converges to
$0$ as $\delta\to 0$. Theorem 1.4 essentially states that if the defect
$\mathrm{d}(\mu_{\delta})$ is small, then the support of $\mu_{\delta}$ is
close to a regular triangular lattice, and it quantifies how close. Note that
the Voronoi tessellation generated by the regular triangular lattice is a
regular hexagonal tessellation. The theorem states that the Voronoi
tessellation of $V_{\delta,\alpha}^{1/2}\Omega$ generated by the rescaled
particles $z_{i}$ is close to a regular hexagonal tessellation in the sense
that, except for at most $N_{\delta}c\varepsilon^{1/3}$ Voronoi cells, the
Voronoi cells are hexagons, and it quantifies how far the hexagons are from
being regular. For a _regular_ hexagon of area
$\frac{V_{\delta,\alpha}}{N_{\delta}}$, the distance between the centre of the
hexagon and each vertex is
$\sqrt{\frac{V_{\delta,\alpha}}{N_{\delta}}}\sqrt{\frac{\phantom{|}2\phantom{|}}{3\sqrt{3}}}$,
and the distance between the centre of the hexagon and each edge is
$\sqrt{\frac{V_{\delta,\alpha}}{N_{\delta}}}\sqrt{\frac{\phantom{|}1\phantom{|}}{2\sqrt{3}}}$.
Since $\lim_{\delta\to 0}V_{\delta,\alpha}/N_{\delta}\to 1$, ‘most’ of the
rescaled Voronoi cells $V_{i}$ are ‘close’ to a regular hexagon of area 1.

######  Remark 1.6 (Locality and weaker assumptions on $f$).

Theorems 1.1, 1.2 say that the quantization problems are essentially
independent of $f$, in the sense that the optimal constants
$\frac{2-\alpha}{1-\alpha}c_{6}$ and $c_{6}$ are independent of $f$ and are
determined by the corresponding quantization problems with $f=1$; see Remarks
3.5 and 3.11. The locality of the quantization problems is independent of the
crystallization and is easier to prove. The locality for the constrained
problem was proved by [14] and the locality for the penalised problem follows
easily from this, as we shall see in Section 3.2. Locality results for the
classical quantization problem were proved among others by [20, 45, 53, 74].
We believe that the assumption of lower semi-continuity on $f$ in Theorems
1.1, 1.2 could be relaxed by using the approach in [60], where a locality
result is proved for the related _irrigation problem_ , which concerns the
best approximation of an absolutely continuous probability measure by a one-
dimensional Hausdorff measure supported on a curve.

######  Remark 1.7 ($\alpha\geq 1$).

For $\alpha\geq 1$, the constrained and penalized quantization problems
$\mathrm{m_{c}}(1,L)$ and $\mathrm{m_{p}}(1,\delta)$ do not have a minimizer.
The infimum is zero since both the Wasserstein distance and the entropy can be
sent to zero by sending the number of particles to infinity. In [14] the
authors considered the constraint

$\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}\geq\frac{1}{L}$

for $\alpha>1$. For $f\in L^{\infty}(\Omega)$, $\alpha\in(1,2)\cup(2,\infty)$
they proved that there exists a constant $C_{2,2}(\alpha)$ such that

$\lim_{L\to\infty}L^{\frac{1}{\alpha-1}}\inf\left\\{W^{2}_{2}(f,\mu):\mu\in\mathcal{P}_{\mathrm{d}}(\Omega),\,\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}\geq\frac{1}{L}\right\\}=C_{2,2}(\alpha)\left(\int_{\Omega}f(x)^{\frac{1}{2-\alpha}}\,\mathrm{d}x\right)^{\frac{2-\alpha}{1-\alpha}}.$

See [14, Proposition 3.11(iii), Remark 3.13(iii)]. For $\alpha>2$,
$C_{2,2}(\alpha)=0$. For $\alpha\in(1,2)$, $C_{2,2}(\alpha)$ is not known, but
it satisfies the bounds

$\int_{B}|x|^{2}\,\mathrm{d}x\leq C_{2,2}(\alpha)\leq c_{6}$

where $B$ is the ball of unit area centred at the origin [14, Lemma 3.10].

######  Remark 1.8 (Motivation for the choice of entropy $H_{\alpha}$).

The are several reasons why we chose to study the entropy
$H_{\alpha}(\mu)=\sum_{i}m_{i}^{\alpha}$, both mathematical and from a
modelling point of view.

  * (i)

The functional $\mu\mapsto W_{2}^{2}(f,\mu)+\delta\sum_{i}h(m_{i})$ is lower
semi-continuous if $h(0)=0$, $h(t)\geq 0$, $h$ is lower semi-continuous,
subadditive and $\lim_{t\to 0+}h(t)/t=+\infty$; see [65, Lemma 7.11]. This
includes our entropy $h(m)=m^{\alpha}$. There is evidence, however, that
crystallization does not hold for all entropies in this class, or at least
that optimal configurations consist of particles of different sizes; see [14,
Section 3.4]. In this paper we have found a subclass for which crystallization
holds. It is an open problem to find the largest class of such entropies.

  * (ii)

Functionals of the form $\mu\mapsto W_{2}^{2}(f,\mu)+\delta\sum_{i}h(m_{i})$
arise in models of economic planning; see [24]. For example, consider the
problem of the optimal location of warehouses in a county $\Omega$ with
population density $f$. The measure $\mu=\sum_{i}m_{i}\delta_{z_{i}}$
represents the locations $z_{i}$ and sizes $m_{i}$ of the warehouses. The
Wasserstein term in the functional above penalizes the average distance
between the population and the warehouses, and the entropy term penalizes the
building or running costs of the warehouses. The subadditive nature of the
entropy $H_{\alpha}$ corresponds to an economy of scale, where it is cheaper
to build one warehouses of size $m$ than two of size $m/2$.

  * (iii)

The special case $\alpha=0.5$ arises in a simplified model of a two-phase
fluid, namely a diblock copolymer melt, in two dimensions; see [17]. Here the
entropy $\sqrt{m}$ corresponds to the interfacial length between a droplet of
one phase of area $m$ and the surrounding, dominant phase.

  * (iv)

Finally, from a mathematical perspective, we were inspired to study the
entropy $H_{\alpha}$ by the conjecture of Bouchitté et al. [14, Section 3.6
(ii)].

###  1.2. Sketch of the proofs of Theorems 1.1 & 1.2

We briefly present the main ideas of the paper. We will see that Theorem 1.2
is an easy consequence of Theorem 1.1 (see Section 5), and so here we just
focus on the  ideas behind the proof of Theorem 1.1.  The strategy for proving
Theorem 1.4 is discussed in Section 7.

First we identify the scaling of the penalized quantization error
$\mathrm{m_{p}}(\alpha,\delta)$ as $\delta\to 0$ using the
$\Gamma$-convergence result of [14]. This gives

$\lim_{\delta\to
0}\left[\left(\frac{c_{6}}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}}\mathrm{m_{p}}(\alpha,\delta)\right]=C_{\mathrm{p}}(\alpha)\int_{\Omega}f(x)^{\frac{1}{2-\alpha}}\,\mathrm{d}x$
(18)

where

$C_{\mathrm{p}}(\alpha)=\ \lim_{\delta\to
0}\left[\left(\frac{c_{6}}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}}\min\left\\{\delta\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}+W^{2}_{2}(\mathbbm{1}_{Q},\mu)\,:\,\mu\in\mathcal{P}_{\mathrm{d}}(Q)\right\\}\right]$
(19)

and $Q=[-1/2,1/2]^{2}$; see Corollary 3.10 and Remark 3.11. The main challenge
in this paper is to show that the optimal constant is
$C_{\mathrm{p}}(\alpha)=c_{6}(2-\alpha)/(1-\alpha)$ for all
$\alpha\in(-\infty,\overline{\alpha}]$. Thanks to equations (18) and (19), to
prove Theorem 1.1 it is sufficient to prove it for the case where $\Omega=Q$
and $f=\mathbbm{1}_{\Omega}$.

Next we prove a monotonicity result (Lemma 3.12), which is analogous to a
monotonicity result proved by [14] for the constrained quantization problem,
which asserts that if Theorem 1.1 holds for some
$\widetilde{\alpha}\in(-\infty,1)$, then it holds for all
$\alpha\in(-\infty,\widetilde{\alpha}]$. Therefore we only need to prove
Theorem 1.1 for the single value $\alpha=\overline{\alpha}=0.583$. Therefore
for the rest of the paper we can take $\Omega=Q$, $f=\mathbbm{1}_{\Omega}$,
$\alpha=\overline{\alpha}$ without loss of generality.

From the definition of the Wasserstein distance, equation (2), if
$\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}$, then

$W_{2}^{2}(\mathbbm{1}_{Q},\mu)=\sum_{i=1}^{N_{\mu}}\int_{T^{-1}(\\{z_{i}\\})}|x-z_{i}|^{2}\,\mathrm{d}x,$
(20)

where $T$ is the optimal transport map.  Since $Q$ is a polygonal set, it is
well known (see Lemma 2.1) that the sets $T^{-1}(\\{z_{i}\\})$ are convex
polygons, called _Laguerre cells_.

A classical result by Fejes Tóth (see Lemma 2.3) states that the second moment
of a polygon about any point in the plane is greater than or equal to the
second moment of a regular polygon (with the same area and same number of
edges) about its centre of mass:

$\int_{P(m,n)}|x-z|^{2}\,\mathrm{d}x\geq\int_{R(m,n)}|x|^{2}\,\mathrm{d}x=m^{2}\int_{R(1,n)}|y|^{2}\,\mathrm{d}y=:m^{2}c_{n}$
(21)

where $P(m,n)$ is a polygon with area $m$ and $n$ edges, $R(m,n)$ is a regular
polygon centred at the origin with area $m$ and $n$ edges, and
$z\in\mathbb{R}^{2}$. Combining (20) and (21) gives

$W_{2}^{2}(\mathbbm{1}_{\Omega},\mu)\geq\sum_{i=1}^{N_{\mu}}m_{i}^{2}c_{n_{i}},$
(22)

for all $\mu\in\mathcal{P}_{\mathrm{d}}(\Omega)$, where $n_{i}$ denotes the
number of edges of the polygon $T^{-1}(\\{z_{i}\\})$ and $m_{i}$ denotes its
area. Our proofs are limited to the $p$-Wasserstein metric with $p=2$ since,
for $p\neq 2$, the transport regions $T^{-1}(\\{z_{i}\\})$ are not convex
polygons. Moreover, our proofs are limited to two dimensions since there is no
equivalent statement of Fejes Tóth’s Moment Lemma in higher dimensions (due to
the lack of regular polytopes in higher dimensions).

Next we recall the proof of Theorem 1.2 due to Gruber [43] for the case
$\alpha=0$, which we will adapt to prove Theorem 1.1 (and consequently Theorem
1.2) for general  $\alpha\in(-\infty,\overline{\alpha}]$. It can be shown that
the function

$(m,n)\mapsto g(m,n):=m^{2}c_{n}$

is convex. (Note that $n\mapsto c_{n}$ can be extended from a function on
$\mathbb{N}\cap[3,\infty)$ to a function on $[3,\infty)$; see Lemma 2.3.) If
$\mu$ is a minimizer of $W_{2}^{2}(\mathbbm{1}_{\Omega},\cdot)$ subject to the
constraint $N_{\mu}\leq L$, then clearly $N_{\mu}=L$ (assuming that $L$ is an
integer) since we get the best constrained approximation of
$\mathbbm{1}_{\Omega}$ by taking as many Dirac masses as possible. By
convexity,

$m^{2}c_{n}=g(m,n)\geq g\left(\tfrac{1}{L},6\right)+\nabla
g\left(\tfrac{1}{L},6\right)\cdot\left(m-\tfrac{1}{L},n-6\right)=\frac{c_{6}}{L^{2}}+\frac{2c_{6}}{L}\left(m-\tfrac{1}{L}\right)+\frac{\kappa}{L^{2}}(n-6)$
(23)

where $\kappa:=g_{n}(1,6)=\partial_{n}c_{n}|_{n=6}<0$. Combining equations
(22) and (23) gives

$W_{2}^{2}(\mathbbm{1}_{\Omega},\mu)\geq\sum_{i=1}^{L}\left(\frac{c_{6}}{L^{2}}+\frac{2c_{6}}{L}\left(m_{i}-\tfrac{1}{L}\right)+\frac{\kappa}{L^{2}}(n_{i}-6)\right)=\frac{c_{6}}{L}+\frac{\kappa}{L^{2}}\sum_{i=1}^{L}(n_{i}-6)$
(24)

since $\sum_{i}m_{i}=|\Omega|=1$. Euler’s formula for planar graphs implies
that the average number of edges in any partition of the unit square $\Omega$
by convex polygons is less than or equal to $6$: $\frac{1}{L}\sum_{i}n_{i}\leq
6$; see Lemma 2.6. Therefore, by equation (24) and since $\kappa<0$,

$L\,\mathrm{m_{c}}(0,L)\geq c_{6}.$

This is the lower bound in Theorem 1.2 for the case $\alpha=0$. A matching
upper bound can be obtained in the limit $L\to\infty$ by taking
$\mu=\sum_{i=1}^{L}\tfrac{1}{L}\delta_{z_{i}}$ where $z_{i}$ lie on a regular
triangular lattice.

In [17] Gruber’s strategy was generalized to prove Theorem 1.1 for the case
$\alpha=0.5$ and $f=1$. Thanks to the results of [14] and our results in
Section 3.2, it follow that Theorem 1.1 holds for all
$\alpha\in(-\infty,0.5]$ and all lower semi-continuous $f$ satisfying (1). In
this paper we extend these ideas further to prove Theorem 1.1 for the case
$\alpha=0.583$, and hence all  $\alpha\in(-\infty,0.583]$. First of all, we
rescale the square $Q$ as follows (see Remark 1.3):

$Q_{\delta,\alpha}:=V_{\delta,\alpha}^{\frac{1}{2}}Q,\qquad
V_{\delta,\alpha}=\left(\frac{c_{6}}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}}.$

The rescaling factor is chosen in such a way that a discrete measure supported
at the centres of regular hexagons of _unit area_ is asymptotically optimal.
Up to a multiplicative factor, the rescaled energy is

$\mathcal{F}_{\delta,\alpha}(\mu):=\frac{c_{6}}{1-\alpha}\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}+W^{2}_{2}(\mathbbm{1}_{Q_{\delta,\alpha}},\mu),$

where $\mathbbm{1}_{Q_{\delta,\alpha}}$ denotes the characteristic function of
the square $Q_{\delta,\alpha}$. Here $\mu$ is a Borel measure on
$Q_{\delta,\alpha}$ of the form $\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}$
with $\sum_{i=1}^{N_{\mu}}m_{i}=V_{\delta,\alpha}$. By (22) we have

$\mathcal{F}_{\delta,\alpha}(\mu)\geq\sum_{i=1}^{N_{\mu}}\left[\frac{c_{6}}{1-\alpha}m_{i}^{\alpha}+m_{i}^{2}c_{n_{i}}\right]=\sum_{i=1}^{N_{\mu}}g_{\alpha}(m_{i},n_{i}),$

where

$g_{\alpha}(m,n):=\frac{c_{6}}{1-\alpha}m^{\alpha}+m^{2}c_{n}.$

Unfortunately, for $\alpha\in(0,1)$, $g_{\alpha}$ is not convex. Our first
main technical result is to show that for $\alpha=\overline{\alpha}$ there
exists $m_{0}>0$ such that the following ‘convexity inequality’ holds for all
$m\geq m_{0}$, $n\in\mathbb{N}\cap[3,\infty)$:

$g_{\overline{\alpha}}(m,n)\geq g_{\overline{\alpha}}(1,6)+\nabla
g_{\overline{\alpha}}(m,n)\cdot(m-1,n-6).$ (25)

See Lemma 4.11, Corollary 4.12 and Corollary 4.16. Our second main technical
result (Lemma 4.15) is to show that if
$\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}$ minimizes
$\mathcal{F}_{\delta,\alpha}$, then

$m_{i}>2.0620\times 10^{-4}>m_{0}.$ (26)

Therefore minimizers satisfy the convexity inequality (25), and the proof of
Theorem 1.1 now follows using Gruber’s strategy.

To be precise, we are only able to prove the inequality (26) for particles
$z_{i}$ that are not too close to the boundary ( Lemma 4.15(i)). Nevertheless,
we are able to prove a worse lower bound on the mass $m_{i}$ of particles near
the boundary ( Lemma 4.15(ii)), which is still sufficient to show that the
number of particles near the boundary is asymptotically negligible. This fixes
what appears to be a gap in the proof in [18], where it was tacitly assumed
that all of the particles were sufficiently far from the boundary of the
rescaled domain (at least distance $3.2143$; see the proof of [18, Lemma 7]).

The idea of the proof of (26) is to compare the energy of a minimizer $\mu$
with that of a competitor $\widetilde{\mu}$ that is obtained by gluing the
smallest particle of $\mu$ with one of its neighbours. The proofs of (25) and
(26) require some delicate positivity estimates. As in the proof of [18], we
also use computer evaluation at several points in the proof to check the sign
of some explicit numerical constants (that are much larger than machine
precision).

###  1.3. Literature on crystallization, optimal partitions and quantization

Our work belongs to the very active research programme of establishing
crystallization results for nonlocal interacting particle systems. This
problem is known as the _crystallization conjecture_ [12]. Despite
experimental evidence that many particle systems, such as atoms in metals,
have periodic ground states, until recently there were few rigorous
mathematical results. Results in one dimension include [11, 39] and results in
two dimensions include [3, 7, 8, 9, 10, 18, 30, 35, 50, 63, 64, 69].  Let us
recall that a central open problem in mathematical physics is to establish the
optimality of the Abrikosov (triangular) lattice for the Ginzburg-Landau
energy [68]. In three dimensions there are few rigorous results. Even
establishing the optimal configuration of just _five_ charges on a sphere was
only achieved in 2013 via a computer-assisted proof [66]. The Kepler
conjecture about optimal sphere packing was also computer-assisted [48, 49],
while the optimal sphere _covering_ remains to this day unknown. In even
higher dimensions (in particular 8 and 24), there start to be more rigorous
results again, e.g., [26, 27, 70]. For a thorough survey of recent
crystallization results for nonlocal particle systems see [12] and [67].

Our result also falls into the field of _optimal partitions_ (see Remark
4.10). The optimality of hexagonal tilings, or _Honeycomb conjectures_ , have
been proved for example by [21, 22, 23, 47]. Kelvin’s problem of finding the
optimal foam in 3D (the ‘three-dimensional Honeycomb conjecture’) remains to
this day unsolved; for over 100 years it was believed that truncated octahedra
gave the optimal tessellation, until the remarkable discovery of a better
tessellation by Weire and Phelan [72].

Finally, our result also belongs to the field of _optimal quantization_ or
_optimal sampling_ [41, 45], [46, Section 33], which concerns the best
approximation of a probability measure by a discrete probability measure. The
most commonly used notion of best approximation is the Wasserstein distance.
This problem has been studied by a wide range of communities including applied
analysis [14, 24, 52], computational geometry [31], discrete geometry [28,
45], and probability [41]. Applications include optimal location of resources
[13], signal and image compression [32, 42], numerical integration [62,
Section 2.3], mesh generation [33, 57], finance [62], materials science [16,
Section 3.2], and particle methods for PDEs (sampling the initial
distribution) [15, Example 7.1].

It is well known that if $\mu=\sum_{i=1}^{N}m_{i}z_{i}$ is a minimizer of
$W_{2}(f\mathrm{d}x,\cdot)$, then the particles $z_{i}$ generate a _centroidal
Voronoi tessellation_ (CVT) [31, 55], which means the particles $z_{i}$ lie at
the centroids of their Voronoi cells. Numerical methods for computing CVTs
include Lloyd’s algorithm [31] and quasi-Newton methods [55]. More generally,
minimizers of the penalized energy
$\mu\mapsto\delta\sum_{i}m_{i}^{\alpha}+W_{2}^{2}(f\mathrm{d}x,\mu)$ generate
_centroidal Laguerre tessellations_ (see Remark 4.6). Numerical methods for
solving the constrained and penalized quantization problems include [19]
(which was used to produce Figures 1 and 2) and [73].

There is a large literature on optimal CVTs of $N$ points (global minima of
$\mu\mapsto W_{2}(\mathbbm{1}_{\Omega},\mu)$ subject to
$\\#\mathrm{supp}(\mu)=N$). According to _Gersho’s conjecture_ (see [40]),
minimizers correspond to regular tessellations consisting of the repetition of
a single polytope whose shape depends only on the spatial dimension. In two
dimensions the polytope is a hexagon [13, 36, 37, 43, 59, 61] and moreover the
result holds for any $p$-Wasserstein metric, $p\in[1,\infty)$. Gersho’s
conjecture is open in three dimensions, although it is believed that the
optimal CVT is a tessellation by truncated octahedra, which is generated by
the body-centred cubic (BCC) lattice. Some numerical evidence for this is
given in [34], and in [6] it was proved that the BCC lattice is optimal among
lattices (but we do not know whether the optimal configuration is in fact a
lattice). Geometric properties of optimal CVTs in 3D were recently proved in
[25], who also suggested a strategy for a computed-assisted proof of Gersho’s
conjecture.

###  1.4. Organization of the paper

In Section 2 we recall some basic notions from optimal transport theory and
convex geometry. In Section 3.1 we recall from [14] the result (9) for the
case $d=p=2$, namely the scaling of the minimum value of the energy for the
constrained problem (11). In Section 3.2 we derive the scaling of the minimum
value of the energy for the penali zed problem (12). These results give the
optimal _scaling_ of the minimum values of the constrained and penalized
energies, but they do not give the optimal constants. In Section 4 we identify
the optimal constant for the penalized problem (which proves Theorem 1.1) and
in Section 5 we identify the optimal constant for the constrained problem
(which proves Theorem 1.2). In Section 6 we prove the asymptotic
crystallization result for all  $\alpha\in(-\infty,1)$ under an additional
assumption.  Finally, Section 7 is devoted to the proof of Theorem 1.4.

##  2\. Preliminaries

###  2.1. Main assumptions

We assume that $\Omega\subset\mathbb{R}^{2}$ is the closure of an open and
bounded set, and $f\in L^{1}(\Omega)$ is a lower semi-continuous function
satisfying $f\geq c>0$ and

$\int_{\Omega}f(x)\,\mathrm{d}x=1.$

###  2.2. Notation

Define  $\mathbb{R}^{+}:=(0,\infty)$. For a Lebesgue-measurable set
$A\subset\mathbb{R}^{2}$, we denote by $|A|$ its area and by $\mathbbm{1}_{A}$
its characteristic function. We let $\mathcal{M}(X)$ denote the set of non-
negative finite Borel measures on $X\subset\mathbb{R}^{d}$ and
$\mathcal{P}(X)\subset\mathcal{M}(X)$ denote the set of probability measures
on $X$. Moreover, we let $\mathcal{M}_{\mathrm{d}}(X)\subset\mathcal{M}(X)$ be
the following set of discrete measures:

$\mathcal{M}_{\mathrm{d}}(X):=\left\\{\sum_{i=1}^{N}m_{i}\delta_{z_{i}}:N\in\mathbb{N},\,m_{i}>0,\,z_{i}\in
X,\,z_{i}\neq z_{j}\textrm{ if }i\neq j\right\\}.$

Recall that $\mathcal{P}_{\mathrm{d}}(X)$ denotes the set of discrete
probability measures,
$\mathcal{P}_{\mathrm{d}}(X)=\mathcal{M}_{\mathrm{d}}(X)\cap\mathcal{P}(X)$,
and that, for $\mu\in\mathcal{P}_{\mathrm{d}}(\Omega)$,
$N_{\mu}:=\\#\mathrm{supp}(\mu)$. For brevity, in an abuse of notation, we
denote the preimage of a singleton set $\\{z\\}\subset X$ under a map $T:X\to
X$ by $T^{-1}(z)$ instead of $T^{-1}(\\{z\\})$.

###  2.3. Facts from optimal transport theory and convex geometry

We start by recalling the characterization of solutions of the semi-discrete
transport problem (2) for the case $p=2$. The following result goes back to
[4] and is now well-known in the optimal transport community; see for example
[54, 56, 58].

######  Lemma 2.1 (Characterization of the optimal transport map).

Let $U\subset\mathbb{R}^{2}$ be a convex polygon,
$\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}\in\mathcal{P}_{\mathrm{d}}(U)$,
$g\in L^{1}(U;\mathbb{R}^{+})$, $\int_{U}g\,\mathrm{d}x=1$, and $W_{2}(g,\mu)$
be the Wasserstein metric

$W_{2}(g,\mu)\>=\inf\left\\{\int_{U}|x-T(x)|^{2}g(x)\,\mathrm{d}x\,:\,T:U\to\\{z_{i}\\}_{i=1}^{N_{\mu}}\textrm{
is
Borel},\,\int_{T^{-1}(z_{i})}g(x)\,\mathrm{d}x=m_{i}\,\forall\,i\right\\}^{\frac{1}{2}}.$

Then the infimum is attained and the minimizer
$T:U\to\\{z_{i}\\}_{i=1}^{N_{\mu}}$ is unique (up to a set of measure zero).
Moreover, by possibly modifying $T$ on a set of measure zero, there exists
$(w_{1},\dots,w_{N_{\mu}})\in\mathbb{R}^{N_{\mu}}$ such that

$\overline{T^{-1}(z_{i})}=\left\\{z\in
U:|z-z_{i}|^{2}-w_{i}\leq|z-z_{j}|^{2}-w_{j}\text{ for all
}j=1,\dots,N_{\mu}\right\\}.$

######  Remark 2.2 (Laguerre cells).

The previous lemma implies that the partition
$\\{\overline{T^{-1}(z_{i})}\\}_{i=1}^{N_{\mu}}$ is the _Laguerre
tessellation_ or _power diagram_ generated by the weighted points
$\\{(z_{i},w_{i})\\}_{i=1}^{N_{\mu}}$; see [5, 58]. The sets
$\overline{T^{-1}(z_{i})}$ are convex polygons, known as _Laguerre cells_ or
_power cells_.

We now recall a classical result by L. Fejes Tóth (see [37, p. 198]), which
says that the minimal second moment of an $n$-gon is greater than or equal to
the minimal second moment of a _regular_ $n$-gon of the same area:

######  Lemma 2.3 (Fejes Tóth’s Moment Lemma).

For $n\in\mathbb{N}$, $n\geq 3$, define

$c_{n}:=\inf\left\\{\min_{\xi\in\mathbb{R}^{2}}\int_{P}|x-\xi|^{2}\mathrm{d}x:P\text{
is an $n$-gon},\,|P|=1\right\\}.$

Then the infimum is attained by a regular $n$-gon. Consequently a direct
calculation gives

$c_{n}=\frac{1}{2n}\left(\frac{1}{3}\tan\frac{\pi}{n}+\cot\frac{\pi}{n}\right).$
(27)

######  Remark 2.4.

Note that a change of variables gives

$\inf\left\\{\min_{\xi\in\mathbb{R}^{2}}\int_{P}|x-\xi|^{2}\mathrm{d}x:P\text{
is an $n$-gon},\,|P|=m\right\\}=c_{n}m^{2}$

for all $m>0$.

We extend the definition of $c_{n}$ to all $n\in[3,\infty)$ using equation
(27).  Its main properties are stated in the next result, whose proof is a
direct computation (see [43]).

######  Lemma 2.5 (Properties of $c_{n}$).

The function $n\mapsto c_{n}$, $n\in[3,\infty)$, is convex and decreasing.
Moreover

$\lim_{n\to\infty}c_{n}=c_{\infty}:=\frac{1}{2\pi}.$

Finally, we recall one more result from convex geometry, which follows from
Euler’s polytope formula. It is proved for example in [18, Lemma 4] or [59,
Lemma 3.3].

######  Lemma 2.6 (Partitions by convex polygons).

Let $U\subset\mathbb{R}^{2}$ be a convex polygon with at most 6 sides. In any
partition of $U$ by convex polygons, the average number of edges per polygon
is less than or equal to $6$.

##  3\. Scaling of the asymptotic quantization error

###  3.1. The constrained optimal location problem

We report here a result about the asymptotic quantization error from [14].

######  Definition 3.1 (Young measures).

Given $\varepsilon>0$ and a measure $\mu\in\mathcal{P}_{\mathrm{d}}(\Omega)$
of the form

$\mu=\sum_{i=1}^{N_{\mu}}m_{i}{\color[rgb]{0,0,0}{\delta_{z_{i}}}},$

define the measures $\rho(\mu)\in\mathcal{P}_{\mathrm{d}}(\mathbb{R}^{+})$ and
$\lambda_{\varepsilon}(\mu)\in\mathcal{M}_{\mathrm{d}}(\Omega\times\mathbb{R}^{+})$
by

$\rho(\mu):=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{m_{i}},\quad\quad\lambda_{\varepsilon}(\mu):=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{\left(z_{i},\frac{m_{i}}{\varepsilon^{2}}\right)}.$

Observe that the first marginal of $\lambda_{\varepsilon}(\mu)$ is $\mu$ and
that the second marginal of $\lambda_{1}(\mu)$ is $\rho(\mu)$.

In order to define the cell formula for the asymptotic quantization error, we
need to introduce the following metric on the space of probability measures.
Given $\rho_{1},\rho_{2}\in\mathcal{P}(\mathbb{R}^{+})$, we define

$\mathrm{d}_{\mathrm{BL}}(\rho_{1},\rho_{2}):=\sup\left\\{\int_{\mathbb{R}^{+}}\varphi\,d(\rho_{1}-\rho_{2}):\varphi\in\mathrm{Lip}(\mathbb{R}^{+}),\,|\varphi|_{\infty}+\mathrm{Lip}(\varphi)\leq
1\right\\},$

where $\mathrm{Lip}(\mathbb{R}^{+})$ is the space of Lipschitz continuous
functions on $\mathbb{R}^{+}$ and $\mathrm{Lip}(\varphi)$ denotes the
Lipschitz constant of $\varphi$. It is well known that
$\mathrm{d}_{\mathrm{BL}}$ metrizes tight convergence (see [29, Theorem
11.3.3]).

The energy density of the asymptotic quantization error is introduced as
follows.

######  Definition 3.2 (Cell formula).

Given $t>0$ and $\rho\in\mathcal{P}(\mathbb{R}^{+})$, define

$G_{t}(\rho):=\inf_{k>0}\frac{S_{t}(\rho,Q_{k})}{k^{2}}$

where $Q_{k}:=[-k/2,k/2]^{2}\subset\mathbb{R}^{2}$ and

$S_{t}(\rho,Q_{k}):=\inf\left\\{W^{2}_{2}(\mathbbm{1}_{Q_{k}},\mu)+\frac{k^{2}}{t^{2}}\mathrm{d}_{\mathrm{BL}}(\rho,\rho(\mu)):\mu\in\mathcal{P}_{\mathrm{d}}(Q_{k})\right\\}.$

Define $G:\mathcal{P}(\mathbb{R}^{+})\to\mathbb{R}$ by

$G(\rho):=\sup_{t>0}G_{t}(\rho)=\lim_{t\to 0}G_{t}(\rho).$

Given $\lambda\in\mathcal{M}(\Omega\times\mathbb{R}^{+})$, let
$\pi_{1}\\#\lambda$ denote its first marginal, where
$\pi_{1}:\Omega\times\mathbb{R}^{+}\to\Omega$ is the projection
$\pi_{1}(x,t)=x$. One of the main results of Bouchitté, Jimenez and Mahadevan
[14, Theorem 3.1] is the following:

######  Theorem 3.3 (Gamma-limit of the quantization error).

For $\varepsilon>0$, let

$\mathcal{E}_{\varepsilon}(\lambda):=\begin{cases}\frac{1}{\varepsilon^{2}}W^{2}_{2}(f,\mu)&\text{if
}\lambda=\lambda_{\varepsilon}(\mu),\,\mu\in\mathcal{P}_{\mathrm{d}}(\Omega),\\\
+\infty&\text{otherwise.}\end{cases}$ (28)

Then
$\mathcal{E}_{\varepsilon}\stackrel{{\scriptstyle\Gamma}}{{\rightarrow}}\mathcal{E}_{0}$
with respect to tight convergence on $\mathcal{M}(\Omega\times\mathbb{R}^{+})$
where

$\mathcal{E}_{0}(\lambda):=\begin{cases}\displaystyle\int_{\Omega}G(\lambda^{x})\,\mathrm{d}x&\text{if
}\lambda=f\mathrm{d}x\otimes\lambda^{x},\\\
+\infty&\text{otherwise,}\end{cases}$

where $f\mathrm{d}x\otimes\lambda^{x}$ denotes the disintegration of $\lambda$
with respect to $f\mathrm{d}x$; see [2, Theorem 2.28].

Bouchitté, Jimenez and Mahadevan used Theorem 3.3 to prove the following
result about the scaling of the asymptotic quantization error for the
constrained optimal location problem; see [14, Lemma 3.10, Proposition
3.11(i)] .

######  Corollary 3.4 (Asymptotic quantization error for the constrained
problem).

For all  $\alpha\in(-\infty,1)$,

$\lim_{L\to\infty}\left[L^{\frac{1}{1-\alpha}}\,\mathrm{m_{c}}(\alpha,L)\right]=C_{\mathrm{c}}(\alpha)\left(\int_{\Omega}f(x)^{\frac{1}{2-\alpha}}\,\mathrm{d}x\right)^{\frac{2-\alpha}{1-\alpha}}$

where

$C_{\mathrm{c}}(\alpha):=\min\left\\{G(\rho):\rho\in\mathcal{P}(\mathbb{R}^{+}),\,\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\rho(t)\leq
1\right\\}.$ (29)

Moreover, the function $\alpha\mapsto C_{\mathrm{c}}(\alpha)$ is non-
increasing.

Note that the result proved in [14] holds more generally: in any dimension,
for any $p$-Wasserstein metric, and for more general entropies.

######  Remark 3.5.

Let $Q\subset\mathbb{R}^{2}$ be a unit square. Taking $\Omega=Q$ and
$f=\mathbbm{1}_{Q}$ in Corollary 3.4 yields

$C_{\mathrm{c}}(\alpha)=\lim_{L\to\infty}L^{\frac{1}{1-\alpha}}\,\inf\left\\{W^{2}_{2}(\mathbbm{1}_{Q},\mu):\mu\in\mathcal{P}_{\mathrm{d}}(Q),\,\,\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}\leq
L\right\\}.$ (30)

######  Remark 3.6 (Optimal constant).

The constant $C_{\mathrm{c}}(\alpha)$ in Corollary 3.4 was known explicitly
for the case  $\alpha\in(-\infty,0]$, where
$C_{\mathrm{c}}(\alpha)=C_{\mathrm{c}}(0)=G(\delta_{1})=c_{6}$ for all
$\alpha\leq 0$. We briefly recall the proof: By Fejes Tóth’s Theorem on Sums
of Moments [43],

$c_{6}=C_{\mathrm{c}}(0)\stackrel{{\scriptstyle\eqref{eq:DefCcalpha}}}{{\leq}}G(\delta_{1})\leq
c_{6}$

where the final inequality follows from [14, Prop. 3.2(iv)].  Therefore
$C_{\mathrm{c}}(0)=c_{6}$. In addition, $C_{\mathrm{c}}(\alpha)\geq
C_{\mathrm{c}}(0)=c_{6}$ for all $\alpha\leq 0$ by the monotonicity of the map
$\alpha\mapsto C_{\mathrm{c}}(\alpha)$ (see Corollary 3.4). On the other hand,
$C_{\mathrm{c}}(\alpha)\leq c_{6}$ by [14, Prop. 3.2(iv)]. We conclude that
$C_{\mathrm{c}}(\alpha)=c_{6}$ for all $\alpha\leq 0$, as required. One of our
contributions is to prove that $C_{\mathrm{c}}(\alpha)=c_{6}$ for all
$\alpha\in(-\infty,0.583]$; see Section 5.

###  3.2. The penalized optimal location problem

Here we prove analogous results to those presented in the previous section.

######  Definition 3.7 (penalized energy).

Let $\delta>0$ and  $\alpha\in(-\infty,1)$. Define
$\mathcal{E}_{\delta,\alpha}:\mathcal{P}_{\mathrm{d}}(\Omega)\to[0,\infty)$ by

$\mathcal{E}_{\delta,\alpha}(\mu):=\delta\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}+W^{2}_{2}(f,\mu)$

where $\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}$.

######  Proposition 3.8 (Gamma-limit of the penalized energy).

Let $\delta>0$,  $\alpha\in(-\infty,1)$ and

$\varepsilon_{\delta,\alpha}:=\left(\frac{\delta(1-\alpha)}{c_{6}}\right)^{\frac{1}{2(2-\alpha)}}.$

Define the rescaled penalized energy
$\widetilde{\mathcal{E}}_{\delta,\alpha}:\mathcal{M}(\Omega\times\mathbb{R}^{+})\to[0,\infty]$
by

$\widetilde{\mathcal{E}}_{\delta,\alpha}(\lambda):=\begin{cases}\varepsilon_{\delta,\alpha}^{-2}\,\mathcal{E}_{\delta,\alpha}(\mu)&\text{if
}\lambda=\lambda_{\varepsilon_{\delta,\alpha}}(\mu),\,\mu\in\mathcal{P}_{\mathrm{d}}(\Omega),\\\
+\infty&\text{otherwise.}\end{cases}$

Then
$\widetilde{\mathcal{E}}_{\delta,\alpha}\stackrel{{\scriptstyle\Gamma}}{{\rightarrow}}\mathcal{G}_{\alpha}$
as $\delta\to 0$ with respect to tight convergence on
$\mathcal{M}(\Omega\times\mathbb{R}^{+})$ where

$\mathcal{G}_{\alpha}(\lambda):=\begin{cases}\displaystyle\int_{\Omega}\left[G(\lambda^{x})+f(x)\frac{c_{6}}{1-\alpha}\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\lambda^{x}(t)\right]\,\mathrm{d}x&\text{if
}\lambda=f\mathrm{d}x\otimes\lambda^{x},\\\
+\infty&\text{otherwise}.\end{cases}$

To prove Proposition 3.8 we need the following technical result from [14,
Lemma 6.3], which says that we can modify $\mu$ to remove asymptotically small
Dirac masses (as $\delta\to 0$) without increasing the energy
$\widetilde{\mathcal{E}}_{\delta,\alpha}(\mu)$ too much.

######  Lemma 3.9.

Let
$\lambda=f\mathrm{d}x\otimes\lambda^{x}\in\mathcal{M}(\Omega\times\mathbb{R}^{+})$
satisfy $\mathcal{E}_{0}(\lambda)<\infty$. Then, for every $\gamma>1$, there
exists a decreasing sequence $(t_{k})_{k\in\mathbb{N}}\subset(0,\infty)$,
$t_{k}\to 0$, and a doubly-indexed sequence
$(\lambda_{\varepsilon}^{k})_{\varepsilon>0,k\in\mathbb{N}}\subset\mathcal{M}(\Omega\times\mathbb{R}^{+})$
satisfying the following:

  * (i)

$\lambda_{\varepsilon}^{k}$ is supported in $\Omega\times[t_{k},\infty)$;

  * (ii)

$\limsup_{k\to\infty}\limsup_{\varepsilon\to
0}\|\lambda^{k}_{\varepsilon}-\lambda\|=0$, where $\|\cdot\|$ denotes the
total variation norm on the space of signed measures on
$\Omega\times\mathbb{R}^{+}$;

  * (iii)

for all  $\alpha\in(-\infty,1)$, $k\in\mathbb{N}$,

$\limsup_{\varepsilon\to
0}\int_{\Omega\times(0,\infty)}t^{\alpha-1}\,\mathrm{d}\lambda_{\varepsilon}^{k}(x,t)\leq\int_{\Omega\times(0,\infty)}t^{\alpha-1}\,\mathrm{d}\lambda(x,t);$

  * (iv)

there exist s $\mu_{\varepsilon}^{k}\in\mathcal{P}_{\mathrm{d}}(\Omega)$ such
that $\lambda_{\varepsilon}^{k}=\lambda_{\varepsilon}(\mu_{\varepsilon}^{k})$
and

$\limsup_{k\to\infty}\,\limsup_{\varepsilon\to
0}\,\varepsilon^{-2}\,W_{2}^{2}(f,\mu^{k}_{\varepsilon})\leq\gamma\int_{\Omega}G(\lambda^{x})\,\mathrm{d}x.$

###### Proof of Proposition 3.8.

For $\mu\in\mathcal{P}_{\mathrm{d}}(\Omega)$,
$\lambda=\lambda_{\varepsilon_{\delta,\alpha}}(\mu)$, we can write

$\displaystyle\widetilde{\mathcal{E}}_{\delta,\alpha}(\lambda)$
$\displaystyle=\frac{c_{6}}{1-\alpha}\varepsilon_{\delta,\alpha}^{2(1-\alpha)}\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}+\frac{1}{\varepsilon_{\delta,\alpha}^{2}}W^{2}_{2}(f,\mu)$
$\displaystyle=\frac{c_{6}}{1-\alpha}\int_{\Omega\times(0,\infty)}t^{\alpha-1}\,\mathrm{d}\lambda_{\varepsilon_{\delta,\alpha}}(\mu)(x,t)+\frac{1}{\varepsilon_{\delta,\alpha}^{2}}W^{2}_{2}(f,\mu).$

Since the function $t\mapsto t^{\alpha-1}$ is unbounded, and thus the first
term of $\widetilde{\mathcal{E}}_{\delta,\alpha}(\lambda)$ is not continuous
in $\lambda$, the $\Gamma$-convergence result does not follow directly from
Theorem 3.3 and the stability of $\Gamma$-limits under continuous
perturbations. We therefore reason as follows.

_Step 1: liminf inequality._ Fix $(\delta_{n})_{n\in\mathbb{N}}$ with
$\delta_{n}\to 0$ as $n\to\infty$. Let
$\lambda\in\mathcal{M}(\Omega\times\mathbb{R}^{+})$ and
$(\lambda_{n})_{n\in\mathbb{N}}\subset\mathcal{M}(\Omega\times\mathbb{R}^{+})$
satisfy $\lambda_{n}\to\lambda$ tightly. Without loss of generality we can
assume that

$\liminf_{n\to\infty}\widetilde{\mathcal{E}}_{\delta_{n},\alpha}(\lambda_{n})<\infty.$
(31)

Therefore there exists
$(\mu_{n})_{n\in\mathbb{N}}\subset\mathcal{M}_{\mathrm{d}}(\Omega)$ such that
$\lambda_{n}=\lambda_{\varepsilon_{\delta_{n},\alpha}}(\mu_{n})$. Observe that
$\pi_{1}\\#\lambda_{n}=\mu_{n}$. By (31), and since $W_{2}$ metrizes weak
convergence of measures [65, Theorem 5.9], then $\mu_{n}\to f\mathrm{d}x$ as
$n\to\infty$. Therefore
$\pi_{1}\\#\lambda=\lim_{n\to\infty}\pi_{1}\\#\lambda_{n}=f\mathrm{d}x$. By
the Disintegration Theorem [2, Theorem 2.28] there exists
$\lambda^{x}\in\mathcal{M}(\mathbb{R}^{+})$ satisfying
$\lambda=f\mathrm{d}x\otimes\lambda^{x}$.

For $M>0$ define the continuous bounded function
$g_{M}:(0,\infty)\to\mathbb{R}$ by

$g_{M}(t):=\min\\{t^{\alpha-1},M\\}.$

Then, by using the liminf inequality of Theorem 3.3, we get

$\displaystyle\liminf_{n\to\infty}\widetilde{\mathcal{E}}_{\delta_{n},\alpha}(\lambda_{n})$
$\displaystyle\geq\liminf_{n\to\infty}\left(\frac{c_{6}}{1-\alpha}\int_{\Omega\times(0,\infty)}g_{M}(t)\,\mathrm{d}\lambda_{\varepsilon_{\delta_{n},\alpha}}(\mu_{n})(x,t)+\frac{1}{\varepsilon_{\delta_{n},\alpha}^{2}}W^{2}_{2}(f,\mu_{n})\right)$
$\displaystyle\geq\frac{c_{6}}{1-\alpha}\int_{\Omega}\left(\int_{0}^{\infty}g_{M}(t)\,\mathrm{d}\lambda^{x}(t)\right)f(x)\,\mathrm{d}x+\int_{\Omega}G(\lambda^{x})\,\mathrm{d}x.$

Since the function $g_{M}$ is non-negative and pointwise non-decreasing in
$M$, we obtain the liminf inequality by passing to the limit $M\to\infty$
using the Monotone Convergence Theorem.

_Step 2: limsup inequality._ Let
$\lambda=f\mathrm{d}x\otimes\lambda^{x}\in\mathcal{M}(\Omega\times\mathbb{R}^{+})$
satisfy $\mathcal{G}_{\alpha}(\lambda)<\infty$, which implies that
$\mathcal{E}_{0}(\lambda)<\infty$. Let $\gamma>1$. By Lemma 3.9(iii),(iv),
there exists a decreasing sequence
$(t_{k})_{k\in\mathbb{N}}\subset(0,\infty)$, a sequence $\delta_{n}\to 0$, and
a doubly-indexed sequence
$(\lambda_{\varepsilon_{\delta_{n},\alpha}}^{k})_{n,k\in\mathbb{N}}\subset\mathcal{M}(\Omega\times\mathbb{R}^{+})$
such that

$\limsup_{k\to\infty}\,\limsup_{n\to\infty}\,\widetilde{\mathcal{E}}_{\delta_{n},\alpha}\left(\lambda_{\varepsilon_{\delta_{n},\alpha}}^{k}\right)\leq\frac{c_{6}}{1-\alpha}\int_{\Omega\times(0,\infty)}t^{\alpha-1}\,\mathrm{d}\lambda(x,t)+\gamma\int_{\Omega}G(\lambda^{x})\,\mathrm{d}x\leq\gamma\mathcal{G}_{\alpha}(\lambda).$

By a diagonalization argument and Lemma 3.9(ii), we can find a subsequence
$\delta_{n}$ (not relabelled) such that
$\lambda_{\varepsilon_{\delta_{n},\alpha}}^{k_{n}}\to\lambda$ tightly as
$n\to\infty$ and

$\limsup_{n\to\infty}\,\widetilde{\mathcal{E}}_{\delta_{n},\alpha}\left(\lambda_{\varepsilon_{\delta_{n},\alpha}}^{k_{n}}\right)\leq\gamma\mathcal{G}_{\alpha}(\lambda).$

Since $\gamma>1$ is arbitrary, the limsup inequality follows. ∎

######  Corollary 3.10 (Asymptotic quantization error for the penalized
problem).

For all  $\alpha\in(-\infty,1)$,

$\lim_{\delta\to
0}\left[\left(\frac{c_{6}}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}}\mathrm{m_{p}}(\alpha,\delta)\right]=C_{\mathrm{p}}(\alpha)\int_{\Omega}f(x)^{\frac{1}{2-\alpha}}\,\mathrm{d}x$
(32)

where

$C_{\mathrm{p}}(\alpha):=\min\left\\{G(\rho)+\frac{c_{6}}{1-\alpha}\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\rho(t):\rho\in\mathcal{P}(\mathbb{R}^{+})\right\\}.$
(33)

###### Proof.

_Step 1._ The functional $\widetilde{\mathcal{E}}_{\delta,\alpha}$ has at
least one minimizer (by [24, Theorem 2.1]), sequences $(\lambda_{\delta})$
with bounded energy have tightly convergent subsequences (by [14, Theorem
3.1(i)]), and $\widetilde{\mathcal{E}}_{\delta,\alpha}$ $\Gamma$-converges to
$\mathcal{G}_{\alpha}$ (by Proposition 3.8). Therefore a standard result in
the theory of $\Gamma$-convergence implies that the minimum value of
$\widetilde{\mathcal{E}}_{\delta,\alpha}$ converges to the minimum value of
$\mathcal{G}_{\alpha}$:

$\lim_{\delta\to
0}\left[\left(\frac{c_{6}}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}}\mathrm{m_{p}}(\alpha,\delta)\right]=\min_{\mathcal{M}(\Omega\times\mathbb{R}^{+})}\mathcal{G}_{\alpha}.$

We are thus left with proving that

$\min_{\mathcal{M}(\Omega\times\mathbb{R}^{+})}\mathcal{G}_{\alpha}=C_{\mathrm{p}}(\alpha)\int_{\Omega}f(x)^{\frac{1}{2-\alpha}}\,\mathrm{d}x,$
(34)

where $C_{\mathrm{p}}(\alpha)$ is defined in (33).

_Step 2._ For each $x\in\Omega$, define
$\mathcal{G}_{\alpha}^{x}:\mathcal{P}(\mathbb{R^{+}})\to\mathbb{R}$ by

$\mathcal{G}^{x}_{\alpha}(\rho):=G(\rho)+f(x)\frac{c_{6}}{1-\alpha}\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\rho(t).$

By definition, if $\lambda=f\mathrm{d}x\otimes\lambda^{x}$,

$\mathcal{G}_{\alpha}(\lambda)=\int_{\Omega}\mathcal{G}^{x}_{\alpha}(\lambda^{x})\,\mathrm{d}x.$
(35)

For each $x\in\Omega$, $\mathcal{G}^{x}_{\alpha}$ is lower semi-continuous
since $G$ is lower semi-continuous [14, Prop. 3.2(i)] and since
$\rho\mapsto\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\rho(t)$ is lower semi-
continuous [65, Lemma 1.6]. By [14, Prop. 3.2(iv)],

$\gamma_{2,2}\int_{0}^{\infty}t\,\mathrm{d}\rho(t)\leq G(\rho)$

where $\gamma_{2,2}=\int_{B_{1}(0)}|x|^{2}\,\mathrm{d}x$. Therefore, for each
$x\in\Omega$, minimising sequences for $\mathcal{G}^{x}_{\alpha}$ are tight.
Consequently $\mathcal{G}^{x}_{\alpha}$ has at least one minimizer.

We claim that there exits a Borel measurable function
$x\mapsto\rho^{x}\in\mathcal{P}(\mathbb{R}^{+})$, $x\in\Omega$, such that

$\mathcal{G}^{x}_{\alpha}(\rho^{x})=\min_{\mathcal{P}(\mathbb{R}^{+})}\mathcal{G}^{x}_{\alpha}.$
(36)

This will follow from Aumann’s Selection Theorem (see [38, Theorem 6.10]) once
we prove that the graph of the multifunction $\Gamma:\Omega\to
2^{\mathcal{P}(\mathbb{R}^{+})}\setminus\emptyset$, defined by
$\Gamma(x):=\mathrm{argmin}\,\mathcal{G}^{x}_{\alpha}$, belongs to
$\mathcal{B}(\Omega)\otimes\mathcal{B}(\mathcal{P}(\mathbb{R}^{+}))$, the
product $\sigma$-algebra of the Borel sets of $\Omega$ and the Borel sets of
$\mathcal{P(\mathbb{R}^{+})}$. To prove this, we define the function
$\Psi:\mathbb{R}^{+}\times\mathcal{P}(\mathbb{R}^{+})\to\mathbb{R}$ by

$\Psi(s,\rho):=G(\rho)+s\frac{c_{6}}{1-\alpha}\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\rho(t).$

In the following, the target space $\mathbb{R}$ will always be equipped with
the Borel $\sigma$-algebra. For each $\rho\in\mathcal{P}(\mathbb{R}^{+})$, the
function $s\mapsto\Psi(s,\rho)$ is continuous. For each $s\in\mathbb{R}^{+}$,
the function $\rho\mapsto\Psi(s,\rho)$ is lower semi-continuous and hence
$\mathcal{B}(\mathcal{P(\mathbb{R}^{+})})$-measurable. Therefore $\Psi$ is a
Carathéodory function and hence
$\mathcal{B}(\mathbb{R}^{+})\otimes\mathcal{B}(\mathcal{P(\mathbb{R}^{+})})$-measurable
(see, e.g., [1, Lemma 4.51]). Define the composite function
$\Phi:\Omega\times\mathcal{P}(\mathbb{R}^{+})\to\mathbb{R}$ by

$\Phi(x,\rho):=\Psi(f(x),\rho)=\mathcal{G}^{x}_{\alpha}(\rho).$

This is
$\mathcal{B}(\Omega)\otimes\mathcal{B}(\mathcal{P(\mathbb{R}^{+})})$-measurable
since $f$ and $\Psi$ are Borel measurable.

We claim that the map
$x\mapsto\min_{\rho\in\mathcal{P}(\mathbb{R}^{+})}\Phi(x,\rho)$ is
$\mathcal{B}(\Omega)$-measurable. Then
$\overline{\Phi}:\Omega\times\mathcal{P}(\mathbb{R}^{+})\to\mathbb{R}$ defined
by
$\overline{\Phi}(x,\nu):=\min_{\rho\in\mathcal{P}(\mathbb{R}^{+})}\Phi(x,\rho)$
is
$\mathcal{B}(\Omega)\otimes\mathcal{B}(\mathcal{P(\mathbb{R}^{+})})$-measurable
(since $\overline{\Phi}$ is constant in its second argument). The required
$\mathcal{B}(\Omega)\otimes\mathcal{B}(\mathcal{P(\mathbb{R}^{+})})$-measurability
of graph of the multifunction $\Gamma$ then follows by noticing that

$\mathrm{graph}(\Gamma)=(\Phi-\overline{\Phi})^{-1}(\\{0\\}).$

To show that $x\mapsto\min_{\rho\in\mathcal{P}(\mathbb{R}^{+})}\Phi(x,\rho)$
is $\mathcal{B}(\Omega)$-measurable, we write it as the composite function
$x\mapsto
f(x)\mapsto\min_{\rho\in\mathcal{P}(\mathbb{R}^{+})}\Psi(f(x),\rho)$. This is
$\mathcal{B}(\Omega)$-measurable since $x\mapsto f(x)$ is
$\mathcal{B}(\Omega)$-measurable and
$s\mapsto\min_{\rho\in\mathcal{P}(\mathbb{R}^{+})}\Psi(s,\rho)$ is the
pointwise infimum of a family of continuous functions, hence upper semi-
continuous and $\mathcal{B}(\mathbb{R}^{+})$-measurable. This completes the
proof that there exists a Borel measurable function
$x\mapsto\rho^{x}\in\mathcal{P}(\mathbb{R}^{+})$ satisfying (36).

_Step 3._ Define
$\lambda:=f\mathrm{d}x\otimes\rho^{x}\in\mathcal{M}(\Omega\times\mathbb{R}^{+})$,
where $\rho^{x}$ is the minimizer of $\mathcal{G}^{x}_{\alpha}$ constructed in
Step 2 (note that $\lambda$ is well -defined by [2, Definition 2.27] since
$x\mapsto\rho^{x}$ is Borel measurable and hence Lebesgue measurable). By
equations (35), (36), $\lambda$ is a minimizer of $\mathcal{G}_{\alpha}$ and

$\min_{\mathcal{M}(\Omega\times\mathbb{R}^{+})}\mathcal{G}_{\alpha}=\int_{\Omega}\min\left\\{\mathcal{G}^{x}_{\alpha}(\rho):\rho\in\mathcal{P}(\mathbb{R}^{+})\right\\}\,\mathrm{d}x.$
(37)

We now rewrite

$\min\left\\{\mathcal{G}^{x}_{\alpha}(\rho):\rho\in\mathcal{P}(\mathbb{R}^{+})\right\\}$

as follows. For $a>0$, define the dilation
$L^{a}:\mathbb{R}^{+}\to\mathbb{R}^{+}$ by $L^{a}(t):=at$. Let
$\rho\in\mathcal{P}(\mathbb{R}^{+})$ and consider the push-forward
$\rho_{a}:=L^{a}\\#\rho\in\mathcal{P}(\mathbb{R}^{+})$. It was proved in [14,
Prop. 3.2(ii)] that

$G(\rho_{a})=aG(\rho).$ (38)

Note that

$\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\rho_{a}(t)=a^{\alpha-1}\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\rho(t).$
(39)

Fix $x\in\Omega$ and let $a:=f(x)^{-\frac{1}{2-\alpha}}$. By (38) and (39) we
can write

$\mathcal{G}^{x}_{\alpha}(\rho)=G(\rho)+f(x)\frac{c_{6}}{1-\alpha}\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\rho(t)=f(x)^{\frac{1}{2-\alpha}}\left[G(\rho_{a})+\frac{c_{6}}{1-\alpha}\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\rho_{a}(t)\right].$
(40)

Therefore, by using (40) and the definition of $C_{\mathrm{p}}(\alpha)$ (see
(33)), we have that

$\displaystyle\min\left\\{\mathcal{G}^{x}_{\alpha}(\rho):\rho\in\mathcal{P}(\mathbb{R}^{+})\right\\}$
$\displaystyle=\min\left\\{G(\rho)+f(x)\frac{c_{6}}{1-\alpha}\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\rho(t):\rho\in\mathcal{P}(\mathbb{R}^{+})\right\\}$
$\displaystyle=f(x)^{\frac{1}{2-\alpha}}C_{\mathrm{p}}(\alpha)$ (41)

for all $x\in\Omega$. By combining (37) and (41) we prove (34) and conclude
the proof. ∎

######  Remark 3.11.

Let $Q\subset\mathbb{R}^{2}$ be a unit square. Taking $\Omega=Q$ and
$f=\mathbbm{1}_{Q}$ in Corollary 3.10 yields

$C_{\mathrm{p}}(\alpha)=\ \lim_{\delta\to
0}\left(\frac{c_{6}}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}}\min\left\\{\delta\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}+W^{2}_{2}(\mathbbm{1}_{Q},\mu):\mu\in\mathcal{P}_{\mathrm{d}}(Q)\right\\}.$
(42)

By Corollary 3.10, in order to prove Theorem 1.1 it is sufficient to prove
that

$C_{\mathrm{p}}(\alpha)=\frac{2-\alpha}{1-\alpha}\,c_{6}$

for all  $\alpha\in(-\infty,\overline{\alpha}]$. The next result, which is
analogous to the monotonicity of the map $\alpha\mapsto
C_{\mathrm{c}}(\alpha)$, means that in order to prove Theorem 1.1 for all
$\alpha\in(-\infty,\overline{\alpha})$, it is sufficient to prove it for the
single value $\alpha=\overline{\alpha}$.

######  Lemma 3.12 (Monotonicity of the constant $C_{\mathrm{p}}$).

Assume that for some  $\tilde{\alpha}\in(-\infty,1)$,

$C_{\mathrm{p}}(\tilde{\alpha})=\frac{2-\tilde{\alpha}}{1-\tilde{\alpha}}\,c_{6}.$

Then

$C_{\mathrm{p}}(\alpha)=\frac{2-\alpha}{1-\alpha}\,c_{6}$

for every $\alpha<\tilde{\alpha}$.

###### Proof.

Recall from Remark 3.6 that $c_{6}=G(\delta_{1})$. By (33), for all
$\alpha\in(-\infty,1)$,

$C_{\mathrm{p}}(\alpha)\leq
G(\delta_{1})+\frac{c_{6}}{1-\alpha}\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\delta_{1}(t)=c_{6}+\frac{c_{6}}{1-\alpha}=\frac{2-\alpha}{1-\alpha}\,c_{6}.$
(43)

Write
$C_{\mathrm{p}}(\alpha)=\min\\{F(\alpha,\rho):\rho\in\mathcal{P}(\mathbb{R}^{+})\\}$,
where

$F(\alpha,\rho)=G(\rho)+\frac{c_{6}}{1-\alpha}\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\rho(t).$

For all $\rho\in\mathcal{P}(\mathbb{R}^{+})$,  $\alpha\in(-\infty,1)$, we have

$F(\alpha,\rho)-{\color[rgb]{0,0,0}{F(\alpha,\delta_{1})}}=G(\rho)-G(\delta_{1})+c_{6}\int_{0}^{\infty}\frac{t^{\alpha-1}-1}{1-\alpha}\,\mathrm{d}\rho(t).$

Let $\phi(t,\alpha)=(t^{\alpha-1}-1)/(1-\alpha)$ denote the integrand on the
right-hand side. Then

$(1-\alpha)^{2}\partial_{\alpha}\phi(t,\alpha)=t^{\alpha-1}(1+(1-\alpha)\ln
t)-1=:\psi(t,\alpha).$

Since $\partial_{\alpha}\psi(t,\alpha)=(1-\alpha)(\ln t)^{2}t^{\alpha-1}\geq
0$ and $\psi(t,1)=0$, we obtain that $\psi(t,\alpha)\leq 0$ for all
$t\in(0,\infty)$,  $\alpha\in(-\infty,1)$. Therefore
$\partial_{\alpha}\phi\leq 0$ and $\phi$ is non-increasing in $\alpha$.
Consequently the map $\alpha\mapsto
F(\alpha,\rho)-{\color[rgb]{0,0,0}{F(\alpha,\delta_{1})}}$ is non-increasing.

Let  $\tilde{\alpha}\in(\infty,1)$ be such that

$C_{\mathrm{p}}(\tilde{\alpha})=\frac{2-\tilde{\alpha}}{1-\tilde{\alpha}}\,c_{6}={\color[rgb]{0,0,0}{F(\tilde{\alpha},\delta_{1})}}.$

For all $\rho\in\mathcal{P}(\mathbb{R}^{+})$ and all
$\alpha\in(-\infty,\tilde{\alpha}]$,

$F(\alpha,\rho)-{\color[rgb]{0,0,0}{F(\alpha,\delta_{1})}}\geq
F(\tilde{\alpha},\rho)-{\color[rgb]{0,0,0}{F(\tilde{\alpha},\delta_{1})}}\geq
C_{\mathrm{p}}(\tilde{\alpha})-{\color[rgb]{0,0,0}{F(\tilde{\alpha},\delta_{1})}}=0.$

Taking the infimum over $\rho$ gives

$C_{\mathrm{p}}(\alpha)\geq{\color[rgb]{0,0,0}{F(\alpha,\delta_{1})}}=\frac{2-\alpha}{1-\alpha}\,c_{6}.$
(44)

Combining (43) and (44) completes the proof. ∎

##  4\. The penalized optimal location problem: Proof of Theorem 1.1

This section is devoted to the proof of Theorem 1.1. In particular, we prove
that

$C_{\mathrm{p}}(\overline{\alpha})=\frac{2-\overline{\alpha}}{1-\overline{\alpha}}\,c_{6}.$

The upper bound is easy to prove:

######  Lemma 4.1 (Upper bound on $C_{\mathrm{p}}(\alpha)$).

For all  $\alpha\in(-\infty,1)$,

$C_{\mathrm{p}}(\alpha)\leq\frac{2-\alpha}{1-\alpha}\,c_{6}.$

###### Proof.

Recall from Remark 3.6 that $G(\delta_{1})=c_{6}$. Therefore

$C_{\mathrm{p}}(\alpha)\stackrel{{\scriptstyle\eqref{eq:Cp}}}{{\leq}}G(\delta_{1})+\frac{c_{6}}{1-\alpha}\int_{0}^{\infty}t^{\alpha-1}\,\mathrm{d}\delta_{1}(t)=c_{6}+\frac{c_{6}}{1-\alpha}=\frac{2-\alpha}{1-\alpha}\,c_{6}.$

∎

######  Remark 4.2 (Direct proof of the upper bound).

Lemma 4.1 can also be proved without using the result from [14] that
$G(\delta_{1})=c_{6}$. Instead we can start from equation (42) and directly
build a sequence of asymptotically optimal competitors $\mu_{\delta}$
supported on a subset of a triangular lattice. This is done by covering the
square $Q$ with regular hexagons of a suitable size and making the heuristic
calculation from Remark 1.3 rigorous; cf. [18, Lemma 8].

The matching lower bound

$C_{\mathrm{p}}(\overline{\alpha})\geq\frac{2-\overline{\alpha}}{1-\overline{\alpha}}\,c_{6}$
(45)

requires much more work. Owing to Corollary 3.10 and Remark 3.11 we can assume
without loss of generality that

$\Omega=Q=[-1/2,1/2]^{2},\qquad f=\mathbbm{1}_{Q}.$

We will do this throughout the rest of the paper.

###  4.1. Rescaling of the energy and the energy of a partition

To prove (45) it is convenient to rescale the domain $Q$. As $\delta\to 0$,
the optimal masses $m_{i}$ in (42) go to $0$. Following [18], instead of
keeping the domain $Q$ fixed as $\delta\to 0$, we blow up $Q$ in such a way
that the optimal masses $m_{i}$ tend to $1$. The following definition is
motivated by the heuristic calculation given in Remark 1.3.

######  Definition 4.3 (Rescaled domain and energy).

For  $\alpha\in(-\infty,1)$ and $\delta>0$, define

$V_{\delta,\alpha}:=\left(\frac{c_{6}}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}}$

and define the rescaled square domain $Q_{\delta,\alpha}$ by

$Q_{\delta,\alpha}:=V_{\delta,\alpha}^{\frac{1}{2}}Q.$

Moreover, define the set of admissible discrete measures
$\mathcal{A}_{\delta,\alpha}$ by

$\mathcal{A}_{\delta,\alpha}:=\left\\{\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}:N_{\mu}\in\mathbb{N},\,m_{i}>0,\,\sum_{i=1}^{N_{\mu}}m_{i}=V_{\delta,\alpha},\,z_{i}\in
Q_{\delta,\alpha},\,z_{i}\neq z_{j}\textrm{ if }i\neq j\right\\}$

and define the rescaled energy
$\mathcal{F}_{\delta,\alpha}:\mathcal{A}_{\delta,\alpha}\to\mathbb{R}$ by

$\mathcal{F}_{\delta,\alpha}(\mu):=\frac{c_{6}}{1-\alpha}\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}+W_{2}^{2}(\mathbbm{1}_{Q_{\delta,\alpha}},\mu).$
(46)

######  Remark 4.4 (Restating $C_{\mathrm{p}}(\alpha)$ in terms of
$\mathcal{F}_{\delta,\alpha}$).

Let $\mu=\sum_{i}m_{i}\delta_{z_{i}}\in\mathcal{P}_{\mathrm{d}}(Q)$. For
$\alpha\in(-\infty,1)$ and $\delta>0$, define
$\widetilde{z}_{i}:=V_{\delta,\alpha}^{1/2}z_{i}$,
$\widetilde{m}_{i}:=V_{\delta,\alpha}m_{i}$, and
$\widetilde{\mu}_{\delta,\alpha}:=\sum_{i}\widetilde{m}_{i}\delta_{\widetilde{z}_{i}}\in\mathcal{A}_{\delta,\alpha}$.
Then

$V^{-2}_{\delta,\alpha}\mathcal{F}_{\delta,\alpha}(\widetilde{\mu}_{\delta,\alpha})=\delta\sum_{i}m_{i}^{\alpha}+W^{2}_{2}(\mathbbm{1}_{Q},\mu).$
(47)

Therefore, by (42) and (47),

$C_{\mathrm{p}}(\alpha)=\lim_{\delta\to
0}V^{-1}_{\delta,\alpha}\min\left\\{\mathcal{F}_{\delta,\alpha}(\mu):\mu\in\mathcal{A}_{\delta,\alpha}\right\\}.$
(48)

We now state two first-order necessary conditions for minimizers of
$\mathcal{F}_{\delta,\alpha}$. For a proof see, for instance, [17, Theorem
4.5].

######  Lemma 4.5 (Properties of minimizers).

Let
$\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}\in\mathcal{A}_{\delta,\alpha}$ be
a minimizer of $\mathcal{F}_{\delta,\alpha}$. Let $T$ be the optimal transport
map defining $W_{2}(\mathbbm{1}_{Q_{\delta,\alpha}},\mu)$ and let
$(w_{1},\ldots,w_{N_{\mu}})$ be the weights of the corresponding Laguerre
tessellation (see Lemma 2.1).

  * (i)

For all $i\in\\{1,\dots,N_{\mu}\\}$, we have

$w_{i}=-\frac{\alpha}{1-\alpha}c_{6}m_{i}^{\alpha-1}.$

  * (ii)

The point $z_{i}$ is the centroid of the Laguerre cell
$\overline{T^{-1}(z_{i})}$, namely

$z_{i}=\frac{1}{m_{i}}\int_{T^{-1}(z_{i})}x\,\mathrm{d}x.$

In particular, $z_{i}\in T^{-1}(z_{i})$.

######  Remark 4.6 (Centroidal Laguerre tessellations).

Lemma 4.5(ii) implies that minimizers of $\mathcal{F}_{\delta,\alpha}$
generate _centroidal Laguerre tessellations_ , which means that the particles
$z_{i}$ lie at the centroids of their Laguerre cells $T^{-1}(z_{i})$ [19, 73].

In the following it will also be convenient to reason from a geometrical point
of view. Each $\mu\in\mathcal{A}_{\delta,\alpha}$ induces a partition of
$Q_{\delta,\alpha}$ by the Laguerre cells $\overline{T^{-1}(z_{i})}$, where
$T$ is the optimal transport map defining
$W_{2}(\mathbbm{1}_{Q_{\delta,\alpha}},\mu)$. We define a wider class of
partitions as follows:

######  Definition 4.7 (Admissible partitions).

Let $\mathcal{S}_{\delta,\alpha}$ denote the family of partitions of
$Q_{\delta,\alpha}$ of the form $\mathcal{C}=(C_{1},\dots,C_{k})$ where
$k\in\mathbb{N}$, $C_{i}\subset Q_{\delta,\alpha}$ is measurable, and
$\sum_{i=1}^{k}\mathbbm{1}_{C_{i}}=1$ a.e. in $Q_{\delta,\alpha}$.

The advantage of working with partitions instead of measures is that it allows
us to localise the nonlocal energy $\mathcal{F}_{\delta,\alpha}$.

######  Definition 4.8 (Optimal partitions).

Define the partition energy $F:\mathcal{S}_{\delta,\alpha}\to\mathbb{R}$ by

$F(\mathcal{C}):=\sum_{i=1}^{k}\left(\frac{c_{6}}{1-\alpha}|C_{i}|^{\alpha}+\int_{C_{i}}|x-\xi_{C_{i}}|^{2}\,\mathrm{d}x\right),$

where $\xi_{C_{i}}:=\frac{1}{|C_{i}|}\int_{C_{i}}x\,\mathrm{d}x$ is the
centroid of $C_{i}$, $i\in\\{1,\dots,k\\}$. We say that
$\mathcal{C}\in\mathcal{S}_{\delta,\alpha}$ is an _optimal partition_ if it
minimizes $F$.

To each $\mu\in\mathcal{A}_{\delta,\alpha}$ it is possible to associate an
element of $\mathcal{S}_{\delta,\alpha}$ as follows:

######  Definition 4.9 (Partition associated to a discrete measure).

Let $\mu\in\mathcal{A}_{\delta,\alpha}$ be of the form
$\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}$. Define
$\mathcal{C}^{\mu}=(C^{\mu}_{1},\dots,C^{\mu}_{N_{\mu}})\in\mathcal{S}_{\delta,\alpha}$
by

$C^{\mu}_{i}:=\overline{T^{-1}(z_{i})}$

for all $i\in\\{1,\dots,N_{\mu}\\}$, where $T$ is the optimal transport map
defining $W_{2}(\mathbbm{1}_{Q_{\delta,\alpha}},\mu)$.

######  Remark 4.10 (Equivalence of the partition formulation).

It was proved in [18, p. 125] that

$\min\\{\mathcal{F}_{\delta,\alpha}(\mu):\mu\in\mathcal{A}_{\delta,\alpha}\\}=\min\\{F(\mathcal{C}):\mathcal{C}\in\mathcal{S}_{\delta,\alpha}\\}.$

Let $\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}$ be a minimizer of
$\mathcal{F}_{\delta,\alpha}$. For $i\in\\{1,\dots,N_{\mu}\\}$, let $n_{i}$
denote the number of edges of $C_{i}^{\mu}$. Then we can bound the energy from
below as follows:

$\displaystyle\mathcal{F}_{\delta,\alpha}(\mu)=F(\mathcal{C}^{\mu})=\sum_{i=1}^{N_{\mu}}\left(\frac{c_{6}}{1-\alpha}|C^{\mu}_{i}|^{\alpha}+\int_{C^{\mu}_{i}}|x-z_{i}|^{2}\,\mathrm{d}x\right)\geq\sum_{i=1}^{N_{\mu}}\left(\frac{c_{6}}{1-\alpha}|C^{\mu}_{i}|^{\alpha}+c_{n_{i}}|C^{\mu}_{i}|^{2}\right)$

by Lemma 2.3 and Remark 2.4. For  $\alpha\in(-\infty,1)$, define
$g_{\alpha}:[0,\infty)\times[3,\infty)\to\mathbb{R}$ by

$g_{\alpha}(m,n):=\frac{c_{6}}{1-\alpha}m^{\alpha}+c_{n}m^{2}.$

In this notation the lower bound above becomes

$\mathcal{F}_{\delta,\alpha}(\mu)=F(\mathcal{C}^{\mu})\geq\sum_{i=1}^{N_{\mu}}g_{\alpha}(|C_{i}^{\mu}|,n_{i}).$
(49)

In the following section we study the function $g_{\alpha}$.

###  4.2. The convexity inequality

We start by proving a technical result that plays the role of a convexity
inequality for $g_{\alpha}$. We want to show that, for large enough values of
$m$,

$g_{\alpha}(m,n)\geq g_{\alpha}(1,6)+\nabla g_{\alpha}(1,6)\cdot(m-1,n-6).$

Writing this out explicitly gives

$\frac{c_{6}}{1-\alpha}m^{\alpha}+c_{n}m^{2}\geq
c_{6}\left(\frac{2-\alpha}{1-\alpha}\right)m+\kappa(n-6),$ (50)

where

$\kappa:=\partial_{n}c_{n}|_{n=6}=\frac{2\pi}{243}-\frac{5\sqrt{3}}{324}<0.$

For $\alpha\in(0,1)$, define the function
$h_{\alpha}:[0,\infty)\times[3,\infty)\to\mathbb{R}$ to be the difference
between $g_{\alpha}$ and its tangent plane approximation at $(1,6)$:

$\displaystyle h_{\alpha}(m,n):=$ $\displaystyle
g_{\alpha}(m,n)-\left(g_{\alpha}(1,6)+\nabla
g_{\alpha}(1,6)\cdot(m-1,n-6)\right)$ $\displaystyle=$
$\displaystyle\frac{c_{6}}{1-\alpha}m^{\alpha}+c_{n}m^{2}-c_{6}\left(\frac{2-\alpha}{1-\alpha}\right)m-\kappa(n-6).$

Note that in this section we restrict our attention to $\alpha>0$ without loss
of generality since by the monotonicity result (Lemma 3.12) in the end we only
need to consider $\alpha=\overline{\alpha}=0.583$. The typical behaviour of
the function $m\mapsto h_{\alpha}(m,n)$ is depicted in Figure 3. Our aim is to
prove that $h_{\alpha}(m,n)$ is non-negative for all integers $n\geq 3$ for
large enough values of $m$, as suggested by the figure.

Figure 3. Behaviour of the map $m\mapsto h_{\alpha}(m,n)$ for different values
of $n$ and for $\alpha=0.583$. Note that $h_{\alpha}(0,n)<0$ for
$n\in\\{3,4,5\\}$, even if this is not evident from the figure.

######  Lemma 4.11 (Positivity of $h_{\overline{\alpha}}$).

Let $n\geq 3$ be a integer. If $h_{\overline{\alpha}}(m_{1},n)\geq 0$ for some
$m_{1}\geq 0$, then $h_{\overline{\alpha}}(m,n)\geq 0$ for all $m\geq m_{1}$.

Before proving this, we prove the following easy but important corollary,
which allows us to reduce the proof of the convexity inequality
$h_{\overline{\alpha}}(\cdot,n)\geq 0$ for all integers $n\geq 3$ to the
finite number of cases $n\in\\{3,4,5\\}$:

######  Corollary 4.12 (Reduction to $n\in\\{3,4,5\\}$).

Let $n\geq 6$ be an integer. Then $h_{\overline{\alpha}}(m,n)\geq 0$ for all
$m\geq 0$.

###### Proof.

Observe that $h_{\overline{\alpha}}(0,n)=-\kappa(n-6)\geq 0$ for all $n\geq
6$. Therefore the result follows immediately from Lemma 4.11. ∎

On the other hand, $h_{\overline{\alpha}}(0,n)<0$ for $n\in\\{3,4,5\\}$. This
is why in the next section we will need to prove a lower bound on the masses
$m_{i}$ of minimizers of $\mathcal{F}_{\delta,\overline{\alpha}}$ to ensure
the validity of the convexity inequality (50).

###### Proof of Lemma 4.11.

_Step 1._ First we study the shape of the function $m\mapsto h_{\alpha}(m,n)$.
In particular, we show that it has exactly one local minimum point. Its
derivative is

$\partial_{m}h_{\alpha}(m,n)=\frac{\alpha}{1-\alpha}c_{6}m^{\alpha-1}+2c_{n}m-c_{6}\frac{2-\alpha}{1-\alpha}.$
(51)

It is easy to see that $\partial_{m}h_{\alpha}(m,n)$ is strictly convex in $m$
(since $\alpha>0$). Therefore $m\mapsto\partial^{2}_{mm}h_{\alpha}(m,n)$ is
increasing and so $m\mapsto\partial_{m}h_{\alpha}(m,n)$ has at most one
critical point. On the other hand, $\lim_{m\to
0}\partial_{m}h_{\alpha}(m,n)=+\infty$,
$\lim_{m\to\infty}\partial_{m}h_{\alpha}(m,n)=+\infty$. Therefore
$m\mapsto\partial_{m}h_{\alpha}(m,n)$ has exactly one critical point and
$m\mapsto h_{\alpha}(m,n)$ has at most two critical points.

Next we prove that $m\mapsto h_{\alpha}(m,n)$ has exactly two critical points.
It is sufficient to prove that

$\partial_{m}h_{\alpha}(1/2,n)<0$

for all $n\geq 3$ (since $\lim_{m\to 0}\partial_{m}h_{\alpha}(m,n)>0$ and
$\lim_{m\to\infty}\partial_{m}h_{\alpha}(m,n)>0$). We have

$\partial_{m}h_{\alpha}(1/2,n)=c_{6}\frac{\alpha
2^{1-\alpha}-2+\alpha}{1-\alpha}+c_{n}.$ (52)

It is straightforward to check that

$\frac{d}{d\alpha}\frac{\alpha
2^{1-\alpha}-2+\alpha}{1-\alpha}=\frac{\psi(\alpha)}{(1-\alpha)^{2}}$ (53)

with

$\psi(\alpha)=2^{1-\alpha}(1-\alpha\ln 2+\alpha^{2}\ln 2)-1.$

Differentiating again gives

$\psi^{\prime}(\alpha)=q(\alpha)2^{1-\alpha}\ln 2,\qquad
q(\alpha):=-\alpha^{2}\ln 2+(2+\ln 2)\alpha-2.$

The concave quadratic polynomial $q$ has roots $\alpha=1$ and $\alpha=2/\ln
2>2$. Therefore, for all $\alpha\in(0,1)$, $q(\alpha)<0$,
$\psi^{\prime}(\alpha)<0$, and

$\psi(\alpha)\geq\psi(1)=0.$ (54)

From equations (52)–(54) we conclude that
$\alpha\mapsto\partial_{m}h_{\alpha}(1/2,n)$ is increasing. Therefore

$\displaystyle\partial_{m}h_{\alpha}(1/2,n)\leq\lim_{\alpha\to
1}\partial_{m}h_{\alpha}(1/2,n)=\lim_{\alpha\to 1}c_{6}\frac{\alpha
2^{1-\alpha}-2+\alpha}{1-\alpha}+c_{n}=(\ln 2-2)c_{6}+c_{n}.$

Since $n\mapsto c_{n}$ is decreasing (see Lemma 2.5),

$\partial_{m}h_{\alpha}(1/2,n)\leq(\ln 2-2)c_{6}+c_{3}<-0.017<0$

as required.

We have shown that $m\mapsto h_{\alpha}(m,n)$ has exactly two critical points.
The smallest critical point is a local maximum point and the largest critical
point is a local minimum point (since
$m\mapsto\partial^{2}_{mm}h_{\alpha}(m,n)$ is increasing). Let
$\widetilde{m}(\alpha,n)$ denote the local minimum point. To prove the lemma
it is sufficient to prove that

$\varphi(\alpha,n):=h_{\alpha}(\widetilde{m}(\alpha,n),n)\geq 0$ (55)

for $\alpha=\overline{\alpha}$ and for all $n\in\mathbb{N}\cap[3,\infty)$.

_Step 2._ Next we prove (55) for the case $n=6$. A direct computation shows
that $1$ is  a local minimum point of $m\mapsto h_{\alpha}(m,6)$ for all
$\alpha\in(0,1)$. Therefore $\widetilde{m}(\alpha,6)=1$ and
$\varphi(\alpha,6)=h_{\alpha}(1,6)=0$.

_Step 3._ Next we prove (55) for the case $n\in\\{3,4,5,7\\}$. Let

$m_{1}(n):=\begin{cases}0.764&n=3,\\\ 0.946&n=4,\\\ 0.98705&n=5,\\\
1.00516&n=7,\end{cases}\quad\quad m_{2}(n):=\begin{cases}0.765&n=3,\\\
0.947&n=4,\\\ 0.9871&n=5,\\\ 1.00518&n=7.\end{cases}$

Then numerically evaluating $\partial_{m}h_{\overline{\alpha}}$ gives

$\partial_{m}h_{\overline{\alpha}}(m_{1}(n),n)\leq\begin{cases}-8\times
10^{-6}&n=3,\\\ -2\times 10^{-5}&n=4,\\\ -1\times 10^{-6}&n=5,\\\ -4\times
10^{7}&n=7,\end{cases}\quad\quad\partial_{m}h_{\overline{\alpha}}(m_{2}(n),n)\geq\begin{cases}3\times
10^{-5}&n=3,\\\ 8\times 10^{-6}&n=4,\\\ 4\times 10^{-7}&n=5,\\\ 1\times
10^{-7}&n=7.\end{cases}$

Let $n\in\\{3,4,5,7\\}$. By the Intermediate Value Theorem, the map
$m\mapsto\partial h_{\overline{\alpha}}(m,n)$ has a root between $m_{1}(n)$
and $m_{2}(n)$. Moreover, since
$\partial_{m}h_{\overline{\alpha}}(m_{1}(n),n)<0$, we have bracketed the
largest root $\widetilde{m}(\overline{\alpha},n)$:
$m_{1}(n)<\widetilde{m}(\overline{\alpha},n)<m_{2}(n)$. Therefore

$\displaystyle\varphi(\overline{\alpha},n)\geq\frac{c_{6}}{1-\overline{\alpha}}m_{1}(n)^{\overline{\alpha}}+c_{n}m_{1}(n)^{2}-c_{6}\left(\frac{2-\overline{\alpha}}{1-\overline{\alpha}}\right)m_{2}(n)-\kappa(n-6)\geq\begin{cases}2\times
10^{-2}&n=3,\\\ 3\times 10^{-3}&n=4,\\\ 5\times 10^{-4}&n=5,\\\ 2\times
10^{-4}&n=7,\end{cases}$

which proves (55) for the case $n\in\\{3,4,5,7\\}$.

_Step 4._ Finally, we prove (55) for the case $n\in\mathbb{N}\cap[8,\infty)$.
To do this we prove that $\partial_{n}\varphi(\overline{\alpha},n)>0$ for
$n\geq 7$. Then the result follows from the case $n=7$ proved in Step 3. By
definition of $\widetilde{m}(\alpha,n)$, for all $\alpha\in(0,1)$, we have
$\partial_{m}h_{\alpha}(\widetilde{m}(\alpha,n),n)=0$. Therefore

$\partial_{n}\varphi(\alpha,n)=\frac{\partial h_{\alpha}}{\partial
n}(\tilde{m}(\alpha,n),n)=\widetilde{m}^{2}(\alpha,n)\,\partial_{n}c_{n}-\kappa.$

Since $n\mapsto c_{n}$ is convex (Lemma 2.5), then $\partial_{n}c_{n}$ is
increasing and we get the lower bound

$\partial_{n}\varphi(\alpha,n)\geq\widetilde{m}^{2}(\alpha,n)\,\partial_{n}c_{n}|_{n=7}-\kappa$
(56)

for all $n\geq 7$. We will prove below that

$\widetilde{m}(\overline{\alpha},n)\leq\frac{3}{2}.$ (57)

Observe that

$\partial_{n}c_{n}=-\frac{1}{n}c_{n}+\frac{1}{2n}\left(-\frac{\pi}{3n^{2}}\sec^{2}\left(\frac{\pi}{n}\right)+\frac{\pi}{n^{2}}\csc^{2}\left(\frac{\pi}{n}\right)\right).$
(58)

From (56), (57), (58) we obtain that

$\displaystyle\partial_{n}\varphi(\overline{\alpha},n)\geq\widetilde{m}^{2}(\overline{\alpha},n)\,\partial_{n}c_{n}|_{n=7}-\kappa\geq\left(\frac{3}{2}\right)^{2}\,(\partial_{n}c_{n})|_{n=7}-\kappa>1.5\times
10^{-5}>0,$

as required.

To prove (57) we reason as follows. Using (51) and the fact that $n\mapsto
c_{n}$ is decreasing (Lemma 2.5), we deduce that
$n\mapsto\partial_{m}h_{\alpha}(m,n)$ is decreasing for all $m$, and hence
$n\mapsto\widetilde{m}(\alpha,n)$ is increasing. Therefore
$\widetilde{m}(\alpha,n)\leq\widetilde{m}(\alpha,\infty)$, where
$\widetilde{m}(\alpha,\infty)$ is defined to be the largest root of

$\partial_{m}h_{\alpha}(m,\infty):=\frac{\alpha}{1-\alpha}c_{6}m^{\alpha-1}+2c_{\infty}m-c_{6}\frac{2-\alpha}{1-\alpha},$

where $c_{\infty}$ was defined in Lemma 2.5. We want to show that
$\widetilde{m}(\overline{\alpha},\infty)\leq 3/2$. We have

$\displaystyle\partial_{m}h_{\overline{\alpha}}\left(1,\infty\right)$
$\displaystyle=\frac{\overline{\alpha}}{1-\overline{\alpha}}c_{6}+2c_{\infty}-c_{6}\frac{2-\overline{\alpha}}{1-\overline{\alpha}}<-0.0024<0,$
$\displaystyle\partial_{m}h_{\overline{\alpha}}\left(3/2,\infty\right)$
$\displaystyle=\frac{\overline{\alpha}}{1-\overline{\alpha}}c_{6}\left(\frac{3}{2}\right)^{\overline{\alpha}-1}+2c_{\infty}\frac{3}{2}-c_{6}\frac{2-\overline{\alpha}}{1-\overline{\alpha}}>0.12>0.$

Therefore $\widetilde{m}(\overline{\alpha},\infty)\in(1,3/2)$ by the
Intermediate Value Theorem. This proves (57) and completes the proof. ∎

######  Remark 4.13.

Despite the fact that we used the specific value of ${\overline{\alpha}}$ in
several places in the proof of Lemma 4.11, we expect Lemma 4.11 to hold for
all $\alpha\in(0,1)$.

###  4.3. Lower bound on the area of optimal cells

Let
$\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}\in\mathcal{A}_{\delta,\overline{\alpha}}$
be a minimizer of $\mathcal{F}_{\delta,\overline{\alpha}}$. We will prove the
convexity inequality $h_{\overline{\alpha}}(m_{i},n)\geq 0$ for all
$i\in\\{1,\ldots,N_{\mu}\\}$, $n\in\mathbb{N}\cap[3,\infty)$. The idea is to
prove a lower bound $m_{i}\geq\overline{m}$ such that
$h_{\overline{\alpha}}(\overline{m},n)\geq 0$ for all
$n\in\mathbb{N}\cap[3,\infty)$. Then the convexity inequality follows from
Lemma 4.11.

We prove the lower bound $m_{i}\geq\overline{m}$ following the strategy of the
proof of [18, Lemma 7], which was developed for the case $\alpha=0.5$. The
main differences are that we have to deal with the more difficult case of
$\alpha=\overline{\alpha}>0.5$ and that we optimise some of the estimates. Our
proof can be used to give a lower bound $\overline{m}$ on the areas $m_{i}$
for all $\alpha\in(0,1)$,  but this lower bound does not satisfy the convexity
inequality $h_{\alpha}(\overline{m},n)\geq 0$ if $\alpha>\overline{\alpha}$.
Our lower bound on the area of the cells holds for cells with arbitrarily many
sides, although by Corollary 4.12 we only need the lower bound for cells with
$3$, $4$ or $5$ sides. We saw no advantage in the proof of restricting the
number of sides.

The following result gives the difference in energy of a partition and the one
obtained by merging two of its cells. Recall that
$\mathcal{S}_{\delta,\alpha}$ and $F$ were defined in Definitions 4.7 and 4.8.

######  Lemma 4.14 (Merging).

Let $\mathcal{C}=(C_{1},\dots,C_{k})\in\mathcal{S}_{\delta,\alpha}$, $k\geq
2$. For $i\in\\{1,\dots,k\\}$ let $m_{i}=|C_{i}|$ and let $z_{i}\in C_{i}$ be
the centroid of $C_{i}$. Define $\mathcal{D}\in\mathcal{S}_{\delta,\alpha}$ by
$\mathcal{D}:=(C_{1}\cup C_{2},C_{3},\dots,C_{k})$. For all
$\alpha\in(-\infty,1)$,

$F(\mathcal{D})-F(\mathcal{C})=\frac{c_{6}}{1-\alpha}\left((m_{1}+m_{2})^{\alpha}-m_{1}^{\alpha}-m_{2}^{\alpha}\right)+|z_{2}-z_{1}|^{2}\frac{m_{1}m_{2}}{m_{1}+m_{2}}.$
(59)

###### Proof.

By definition

$z_{1}=\frac{1}{m_{1}}\int_{C_{1}}x\,\mathrm{d}x,\quad\quad
z_{2}=\frac{1}{m_{2}}\int_{C_{2}}x\,\mathrm{d}x.$

Let $\overline{z}\in C_{1}\cup C_{2}$ be the centroid of $C_{1}\cup C_{2}$:

$\bar{z}=\frac{m_{1}}{m_{1}+m_{2}}z_{1}+\frac{m_{2}}{m_{1}+m_{2}}z_{2}.$

A direct computation gives

$\displaystyle\int_{C_{1}\cup C_{2}}$
$\displaystyle|x-\bar{z}|^{2}\,\mathrm{d}x-\int_{C_{1}}|x-z_{1}|^{2}\,\mathrm{d}x-\int_{C_{2}}|x-z_{2}|^{2}\,\mathrm{d}x$
$\displaystyle=\int_{C_{1}}\left(|\bar{z}|^{2}-2x\cdot\bar{z}-|z_{1}|^{2}+2x\cdot
z_{1}\right)\,\mathrm{d}x+\int_{C_{2}}\left(|\bar{z}|^{2}-2x\cdot\bar{z}-|z_{2}|^{2}+2x\cdot
z_{2}\right)\,\mathrm{d}x$
$\displaystyle=m_{1}|\bar{z}|^{2}-2m_{1}z_{1}\cdot\bar{z}+m_{1}|z_{1}|^{2}+m_{2}|\bar{z}|^{2}-2m_{2}z_{2}\cdot\bar{z}+m_{2}|z_{2}|^{2}$
$\displaystyle=m_{1}|\bar{z}-z_{1}|^{2}+m_{2}|\bar{z}-z_{2}|^{2}$
$\displaystyle=m_{1}\left|\frac{m_{2}}{m_{1}+m_{2}}(z_{2}-z_{1})\right|^{2}+m_{2}\left|\frac{m_{1}}{m_{1}+m_{2}}(z_{1}-z_{2})\right|^{2}$
$\displaystyle=\frac{m_{1}m_{2}}{m_{1}+m_{2}}|z_{2}-z_{1}|^{2}.$

The result now follows immediately from the definition of $F$. ∎

Figure 4. The construction inside the ball $B_{R}(\bar{z})$ (see the proof of
Lemma 4.15).

We now prove a lower bound on the area of optimal cells, as well as an upper
bound on the diameter of the cells and the maximum distance between the
centroids. The latter two estimates will be used later to deal with the fact
that the lower bound on the area of cells close to the boundary of
$Q_{\delta,\overline{\alpha}}$ is not good enough to ensure the validity of
the convexity inequality (50).

######  Lemma 4.15 (Lower bound on the area of optimal cells).

Let
$\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}\in\mathcal{A}_{\delta,\overline{\alpha}}$
be a minimizer of $\mathcal{F}_{\delta,\overline{\alpha}}$. If $\delta>0$ is
sufficiently small, then the following hold:

  * (i)

If $\mathrm{dist}(z_{i},\partial Q_{\delta,\overline{\alpha}})\geq 4$, then

$m_{i}>\overline{m}:=2.0620\times 10^{-4}.$

  * (ii)

If $\mathrm{dist}(z_{i},\partial Q_{\delta,\overline{\alpha}})<4$, then

$m_{i}>m_{\mathrm{b}}:=1.5212\times 10^{-5}.$

  * (iii)

Let $B\subset Q_{\delta,\overline{\alpha}}$ be a ball of radius $R$. If
$B\cap\mathrm{supp}(\mu)=\emptyset$, then $R<R_{0}:=3.3644$.

  * (iv)

Let $T$ be the optimal transport map defining
$W_{2}(\mathbbm{1}_{Q_{\delta,\overline{\alpha}}},\mu)$. For all
$i\in\\{1,\ldots,N_{\mu}\\}$,

$\mathrm{diam}(T^{-1}(z_{i}))\leq
D_{0}:=2\left(8R_{0}^{2}+\frac{\overline{\alpha}}{1-\overline{\alpha}}c_{6}m_{\mathrm{b}}^{\overline{\alpha}-1}\right)^{\frac{1}{2}}.$

###### Proof.

_Step 1: Upper bound on the distance between Dirac masses._ Let
$\bar{z}\in{\rm supp}(\mu)$ satisfy $\mathrm{dist}(\bar{z},\partial
Q_{\delta,\overline{\alpha}})\geq 4$. Take $R\in(0,4)$ such that
$B_{R}(\bar{z})\cap{\rm supp}(\mu)=\\{\bar{z}\\}$. We want to get an upper
bound on $R$. Let $S:B_{R}(\bar{z})\to{\rm supp}(\mu)$ be any Borel map. Then

$\displaystyle\int_{B_{R}(\bar{z})}|x-S(x)|^{2}\,\mathrm{d}x$
$\displaystyle=\int_{B_{R/2}(\bar{z})}|x-S(x)|^{2}\,\mathrm{d}x+\int_{B_{R}(\bar{z})\setminus
B_{R/2}(\bar{z})}|x-S(x)|^{2}\,\mathrm{d}x$
$\displaystyle\geq\int_{B_{R/2}(\bar{z})}|x-\bar{z}|^{2}\,\mathrm{d}x+\int_{B_{R}(\bar{z})\setminus
B_{R/2}(\bar{z})}\Big{|}x-R\frac{x}{|x|}\Big{|}^{2}\,\mathrm{d}x$
$\displaystyle=\frac{\pi}{12}R^{4}.$ (60)

It is now convenient to use the partition energy $F$. Let $\mathcal{C}^{\mu}$
be the partition associated to the minimizer $\mu$ (see Definition 4.9).
Consider the partition $\widetilde{\mathcal{C}}\in\mathcal{S}_{\delta,\alpha}$
obtained by modifying $\mathcal{C}^{\mu}$ in the ball $B_{R}(\bar{z})$ as
follows. Write $\mathcal{C}^{\mu}=(C_{1},\ldots,C_{N_{\mu}})$ and define
$\widetilde{C}_{i}=C_{i}\setminus B_{R}(\bar{z})$ for
$i\in\\{1,\ldots,N_{\mu}\\}$. Let $\\{H_{j}\\}$ be a tiling of the plane by
regular hexagons of area $A$, where $A>0$ will be defined below, and let
$\widetilde{H_{j}}=H_{j}\cap B_{R}(\bar{z})$. Define $\widetilde{\mathcal{C}}$
to be the partition consisting of the sets $\widetilde{C}_{i}$ for all
$i\in\\{1,\ldots,N_{\mu}\\}$ and $\widetilde{H}_{j}$ for all $j$ such that
$\widetilde{H_{j}}\neq\emptyset$; see Figure 4.

Let $d_{A}:=2^{\frac{3}{2}}3^{-\frac{3}{4}}A^{\frac{1}{2}}$ be the diameter of
a regular hexagon of area $A$. The number of hexagons $N_{A}$ needed to cover
a ball of radius $R$ is bounded above by

$N_{A}\leq\frac{\pi(R+d_{A})^{2}}{A}.$ (61)

If $H\in\widetilde{\mathcal{C}}$ is a (whole) regular hexagon of area $A$ with
centroid $\xi_{H}$, then

$\frac{c_{6}}{1-\overline{\alpha}}|H|^{\overline{\alpha}}+\int_{H}|x-\xi_{H}|^{2}\,\mathrm{d}x=\frac{c_{6}}{1-\overline{\alpha}}A^{\overline{\alpha}}+c_{6}A^{2}.$
(62)

Since $\mu$ is a minimizer of $\mathcal{F}_{\delta,\overline{\alpha}}$, then
$C^{\mu}$ is a minimizer of $F$. Therefore

$\displaystyle 0$ $\displaystyle\geq
F(\mathcal{C}^{\mu})-F(\widetilde{\mathcal{C}})$
$\displaystyle\geq\sum_{\begin{subarray}{c}i=1\\\ C_{i}\cap
B_{R}(\bar{z})\neq\emptyset\end{subarray}}^{N_{\mu}}\left(\frac{c_{6}}{1-\overline{\alpha}}|C_{i}|^{\overline{\alpha}}+\int_{C_{i}\setminus
B_{R}(\bar{z})}|x-\xi_{C_{i}}|^{2}\,\mathrm{d}x+\int_{C_{i}\cap
B_{R}(\bar{z})}|x-\xi_{C_{i}}|^{2}\,\mathrm{d}x\right)$
$\displaystyle\quad-\sum_{\begin{subarray}{c}i=1\\\ C_{i}\cap
B_{R}(\bar{z})\neq\emptyset\end{subarray}}^{N_{\mu}}\left(\frac{c_{6}}{1-\overline{\alpha}}|C_{i}\setminus
B_{R}(\bar{z})|^{\overline{\alpha}}+\int_{C_{i}\setminus
B_{R}(\bar{z})}|x-\xi_{C_{i}\setminus
B_{R}(\bar{z})}|^{2}\,\mathrm{d}x\right)$ $\displaystyle\quad-
N_{A}\left(\frac{c_{6}}{1-\overline{\alpha}}|H|^{\overline{\alpha}}+\int_{H}|x-\xi_{H}|^{2}\,\mathrm{d}x\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:Hex_energy}}}{{\geq}}\sum_{i=1}^{N_{\mu}}\int_{C_{i}\cap
B_{R}(\bar{z})}|x-\xi_{C_{i}}|^{2}\,\mathrm{d}x-N_{A}\left(\frac{c_{6}}{1-\overline{\alpha}}A^{\overline{\alpha}}+c_{6}A^{2}\right)$
$\displaystyle\quad+\sum_{\begin{subarray}{c}i=1\\\ C_{i}\cap
B_{R}(\bar{z})\neq\emptyset\end{subarray}}^{N_{\mu}}\left(\int_{C_{i}\setminus
B_{R}(\bar{z})}|x-\xi_{C_{i}}|^{2}\,\mathrm{d}x-\int_{C_{i}\setminus
B_{R}(\bar{z})}|x-\xi_{C_{i}\setminus
B_{R}(\bar{z})}|^{2}\,\mathrm{d}x\right)$
$\displaystyle\geq\int_{B_{R}(\bar{z})}|x-S(x)|^{2}\mathrm{d}x-N_{A}\left(\frac{c_{6}}{1-\overline{\alpha}}A^{\overline{\alpha}}+c_{6}A^{2}\right),$
(63)

where $S:B_{R}(\bar{z})\to\mathrm{supp}(\mu)$ is defined by $S(x)=\xi_{C_{i}}$
if $x\in C_{i}$, and where in the final inequality we used the property of the
centroid that

$\int_{C_{i}\setminus B_{R}(\bar{z})}|x-\xi_{C_{i}\setminus
B_{R}(\bar{z})}|^{2}\,\mathrm{d}x=\inf_{y\in\mathbb{R}^{2}}\int_{C_{i}\setminus
B_{R}(\bar{z})}|x-y|^{2}\,\mathrm{d}x.$

Combining estimates (63) and (4.3) gives

$\frac{\pi}{12}R^{4}\leq
N_{A}\left(\frac{c_{6}}{1-\overline{\alpha}}A^{\overline{\alpha}}+c_{6}A^{2}\right)\stackrel{{\scriptstyle\eqref{eq:NA}}}{{\leq}}\frac{\pi(R+d_{A})^{2}}{A}\left(\frac{c_{6}}{1-\overline{\alpha}}A^{\overline{\alpha}}+c_{6}A^{2}\right).$
(64)

Define

$p(R,A):=R^{2}-(R+d_{A})\left(\frac{12c_{6}}{1-\overline{\alpha}}A^{\overline{\alpha}-1}+12c_{6}A\right)^{\frac{1}{2}}.$

Then (64) implies that $p(R,A)\leq 0$. The quadratic polynomial $R\mapsto
p(R,A)$ has one positive root and one negative root. Let $\widetilde{R}(A)$
denote the positive root:

$\widetilde{R}(A):=\frac{1}{2}\left[12c_{6}\left(\frac{A^{\overline{\alpha}-1}}{1-\overline{\alpha}}+A\right)\right]^{\frac{1}{2}}+\frac{1}{2}\sqrt{12c_{6}\left(\frac{A^{\overline{\alpha}-1}}{1-\overline{\alpha}}+A\right)+4\left[12c_{6}\left(\frac{A^{\overline{\alpha}-1}}{1-\overline{\alpha}}+A\right)\right]^{\frac{1}{2}}d_{A}}.$

Since $p(R,A)\leq 0$, we have $R\in[0,\widetilde{R}(A)]$ for all $A$, and so

$R\leq\min_{A>0}\widetilde{R}(A)\leq\widetilde{R}(0.52)<3.3644,$ (65)

where the final inequality was obtained by numerically evaluating
$\widetilde{R}(0.52)$. The choice $A=0.52$ was motivated by numerically
minimising $\widetilde{R}(A)$.

_Step 2: Proof of (i)._ Let $\bar{z}\in\mathrm{supp}(\mu)$ satisfy
$\mathrm{dist}(\bar{z},\partial Q_{\delta,\overline{\alpha}})\geq 4$. Let
$R_{0}=3.3644$. By Step 1, there exists at least one point $z\in
B_{R_{0}}(\bar{z})\cap\mathrm{supp}(\mu)$. In particular,

$|\bar{z}-z|\leq 3.3644.$ (66)

Let $m=\mu(\\{\bar{z}\\})$, $M=\mu(\\{z\\})$. We can assume without loss of
generality that $m\leq M$ (otherwise simply interchange the roles of $\bar{z}$
and $z$).

Let $\mathcal{C}^{\mu}$ be the partition associated to the minimizer $\mu$. We
can define a new partition $\mathcal{D}$ by replacing the cells
$\overline{T^{-1}(\bar{z})}$ and $\overline{T^{-1}(z)}$ with their union. Then
Lemma 4.14 yields

$0\leq
F(\mathcal{D})-F(\mathcal{C}^{\mu})\leq\frac{c_{6}}{1-\overline{\alpha}}\left((m+M)^{\overline{\alpha}}-m^{\overline{\alpha}}-M^{\overline{\alpha}}\right)+|\bar{z}-z|^{2}\frac{mM}{m+M}.$

Define $\lambda:=\frac{m}{M}\in(0,1]$. By dividing the previous inequality by
$M^{\overline{\alpha}}$ and rearranging we obtain

$m\geq\left[\frac{1}{|\bar{z}-z|^{2}}\frac{c_{6}}{1-\overline{\alpha}}\inf_{\lambda\in(0,1]}\left((1+\lambda)\frac{1+\lambda^{\overline{\alpha}}-(1+\lambda)^{\overline{\alpha}}}{\lambda^{\overline{\alpha}}}\right)\right]^{\frac{1}{1-\overline{\alpha}}}.$
(67)

For $\alpha\in(0,1)$, let

$\Theta_{\alpha}(\lambda):=(1+\lambda)\frac{1+\lambda^{\alpha}-(1+\lambda)^{\alpha}}{\lambda^{\alpha}}.$

We can restrict out attention to $\alpha>0$ since eventually we will apply
this result to $\alpha=\overline{\alpha}>0$. We want to bound
$\Theta_{\alpha}$ from below for the case $\alpha=\overline{\alpha}$. The idea
is the following: We first prove in Step 2a that the function
$\lambda\mapsto\Theta_{\alpha}(\lambda)$ has one minimum point for all
$\alpha\in(0,1)$. In Step 2b we estimate this minimum point for the case
$\alpha=\overline{\alpha}$.

_Step 2a._ In this substep we prove that, for all $\alpha\in(0,1)$, the
function $\lambda\mapsto\Theta^{\prime}_{\alpha}(\lambda)$ vanishes at only
one point $\lambda\in[0,1)$. Fix $\alpha\in(0,1)$. We have

$\Theta^{\prime}_{\alpha}(\lambda)=\frac{1}{\lambda^{1+\alpha}}\left[(1-{\alpha})\lambda+\lambda^{1+\alpha}-(\alpha+1)(1+\lambda)^{\alpha}\lambda+\alpha(1+\lambda)^{1+\alpha}-\alpha\right]=:\frac{1}{\lambda^{1+\alpha}}\Lambda(\lambda).$

The strategy we use to prove that there exists a unique $\lambda\in(0,1)$ such
that $\Lambda(\lambda)=0$ is the following: Using the fact that

$\Lambda(0)<0,\quad\quad\Lambda(1)=(1-\alpha)(2-2^{\alpha})>0,\quad\quad\Lambda^{\prime}(0)=-\alpha+\alpha^{2}<0,$

the desired result is proved once we show that $\Lambda^{\prime}$ vanishes at
only one point $\lambda\in(0,1)$. A direct computation gives

$\displaystyle\Lambda^{\prime}(\lambda)$
$\displaystyle=\frac{1}{(1+\lambda)^{1-\alpha}}\left[(1-\alpha)(1+\lambda)^{1-\alpha}+(1+\alpha)\lambda^{\alpha}(1+\lambda)^{1-\alpha}-1+\alpha^{2}-(1+\alpha)\lambda\right]$
$\displaystyle=:\frac{1}{(1+\lambda)^{1-\alpha}}\Phi(\lambda)$

where

$\Phi(\lambda)=(1-\alpha)(1+\lambda)^{1-\alpha}+(1+\alpha)\lambda^{\alpha}(1+\lambda)^{1-\alpha}-1+\alpha^{2}-(1+\alpha)\lambda.$

We claim that

$\Phi(0)<0,\quad\quad\Phi(1)>0,$ (68)

and that

$\Phi^{\prime}(\lambda)>0$ (69)

for all $\lambda\in[0,1)$. This will show that $\Phi$ vanishes at only one
point $\lambda\in(0,1)$ and, in turn, that the same holds for
$\Lambda^{\prime}$.

We start by proving (68). Note that $\Phi(0)=-\alpha+\alpha^{2}<0$ since
$\alpha\in(0,1)$. Let

$\psi(\alpha):=\Phi(1)=2^{2-\alpha}-2-\alpha+\alpha^{2}.$

We want to prove that $\psi(\alpha)>0$. Since $\psi(1)=0$, it is sufficient to
prove that $\psi^{\prime}(\alpha)<0$. Note that
$\psi^{\prime}(\alpha)=-2^{2-\alpha}\ln 2-1+2\alpha$,
$\psi^{\prime\prime}(\alpha)=2^{2-\alpha}(\ln 2)^{2}+2>0$, and
$\psi^{\prime}(1)=-2\ln 2+1<0$. Therefore $\psi(\alpha)>0$ for all
$\alpha\in(0,1)$, which completes the proof of (68).

Finally, we prove (69). We have

$\displaystyle\Phi^{\prime}(\lambda)$
$\displaystyle=(1-\alpha)^{2}(1+\lambda)^{-\alpha}+\alpha(1+\alpha)\lambda^{\alpha-1}(1+\lambda)^{1-\alpha}+(1-\alpha^{2})\lambda^{\alpha}(1+\lambda)^{-\alpha}-(1+\alpha),$
$\displaystyle\Phi^{\prime\prime}(\lambda)$
$\displaystyle=-\alpha(1-\alpha)^{2}(1+\lambda)^{-1-\alpha}-\alpha(1-\alpha^{2})\lambda^{\alpha-2}(1+\lambda)^{-\alpha}(1-\lambda)-\alpha(1-\alpha^{2})\lambda^{\alpha}(1+\lambda)^{-1-\alpha}.$

Since $\Phi^{\prime\prime}(\lambda)<0$ for all $\lambda\in[0,1)$, we have that

$\Phi^{\prime}(\lambda)\geq\Phi^{\prime}(1)=2^{1-\alpha}(1+\alpha^{2})-(1+\alpha)=:\varphi(\alpha).$

We have

$\varphi^{\prime}(\alpha)=-\ln 2(1+\alpha^{2})2^{1-\alpha}+2\alpha
2^{1-\alpha}-1,\quad\varphi^{\prime\prime}(\alpha)=2^{1-\alpha}\left[(\ln
2)^{2}\alpha^{2}-4\alpha\ln 2+2+(\ln 2)^{2}\right].$

Therefore $\varphi^{\prime\prime}(\alpha)=0$ if and only if
$\alpha\in\\{\alpha_{-},\alpha_{+}\\}$, where

$\alpha_{\pm}=\frac{2\pm\sqrt{2-(\ln 2)^{2}}}{\ln 2}.$

Since $1<\alpha_{-}<\alpha_{+}$, $\varphi$ is strictly convex in
$(0,\alpha_{-})$. Therefore, for all $\alpha\in(0,1)$,

$\varphi(\alpha)>\varphi(1)+\varphi^{\prime}(1)(\alpha-1)=(1-2\ln
2)(\alpha-1)>0.$

Therefore $\Phi^{\prime}(\lambda)\geq\varphi(\alpha)>0$, which completes the
proof of (69).

_Step 2b._ Let $\bar{\lambda}\in(0,1)$ denote the unique root of
$\Theta^{\prime}_{\overline{\alpha}}$. We now estimate
$\Theta_{\overline{\alpha}}(\bar{\lambda})=\inf_{\lambda\in(0,1]}\Theta_{\overline{\alpha}}(\lambda)$.
Let $\lambda_{1}=0.160764$ and $\lambda_{2}=0.160767$. Numerically we see that

$\Theta^{\prime}_{\overline{\alpha}}(\lambda_{1})<-2\times
10^{-6}<0,\quad\quad\Theta^{\prime}_{\overline{\alpha}}(\lambda_{2})>2\times
10^{-6}>0.$

Therefore $\bar{\lambda}\in(\lambda_{1},\lambda_{2})$ by the Intermediate
Value Theorem. Recall that

$\Theta^{\prime}_{\overline{\alpha}}(\lambda)=\lambda^{-1-\alpha}[(1-\overline{\alpha})\lambda+\lambda^{1+\overline{\alpha}}+(1+\lambda)^{\overline{\alpha}}(\overline{\alpha}-\lambda)-\overline{\alpha}].$

Therefore, for all $\lambda\in(\lambda_{1},\lambda_{2})$,

$\displaystyle\Theta^{\prime}_{\overline{\alpha}}(\lambda)$
$\displaystyle\leq\lambda_{1}^{-1-\overline{\alpha}}[(1-\overline{\alpha})\lambda_{2}+\lambda_{2}^{1+\overline{\alpha}}+(1+\lambda_{2})^{\overline{\alpha}}(\overline{\alpha}-\lambda_{1})-\overline{\alpha}]<6.2\times
10^{-5}$ $\displaystyle\Theta^{\prime}_{\overline{\alpha}}(\lambda)$
$\displaystyle\geq\lambda_{1}^{-1-\overline{\alpha}}[(1-\overline{\alpha})\lambda_{1}+\lambda_{1}^{1+\overline{\alpha}}+(1+\lambda_{1})^{\overline{\alpha}}(\overline{\alpha}-\lambda_{2})-\overline{\alpha}]>-6.3\times
10^{-5}.$

Therefore $|\Theta^{\prime}_{\overline{\alpha}}(\lambda)|\leq 6.3\times
10^{-5}$ for all $\lambda\in(\lambda_{1},\lambda_{2})$. It follows that

$\Theta_{\overline{\alpha}}(\bar{\lambda})\geq\Theta_{\overline{\alpha}}(\lambda_{1})-(\lambda_{2}-\lambda_{1})\|\Theta^{\prime}_{\overline{\alpha}}\|_{L^{\infty}((\lambda_{1},\lambda_{2}))}\geq
0.85482.$ (70)

From (66), (67) and (70) we conclude that

$m>\left(\frac{1}{(3.3644)^{2}}\cdot\frac{c_{6}}{1-\overline{\alpha}}\cdot
0.85482\right)^{\frac{1}{1-\overline{\alpha}}}>2.0620\times
10^{-4}=\overline{m},$ (71)

which proves (i).

_Step 3: Proof of (iii)._ This is very similar to Step 1. Let
$B=B_{R}(x_{0})\subset Q_{\delta,\overline{\alpha}}$ satisfy
$B\cap\mathrm{supp}(\mu)=\emptyset$. Let $S:B\to{\rm supp}(\mu)$ be any Borel
map. We have

$\int_{B}|x-S(x)|^{2}\,\mathrm{d}x\geq\int_{B}\mathrm{dist}(x,\partial
B)^{2}\,\mathrm{d}x\geq\int_{B}\mathrm{dist}(x,\\{x_{0}\\}\cup\partial
B)^{2}\,\mathrm{d}x\stackrel{{\scriptstyle\eqref{eq:lbW22}}}{{=}}\frac{\pi}{12}R^{4}.$

The second inequality is clearly suboptimal, but it is sufficient for our
purposes. Repeating exactly the same argument used in Step 1 (with
$B_{R}(\bar{z})$ replaced by $B$) gives $R<3.3644$, as required.

_Step 4: Proof of (ii)._ Let $z_{i}\in\mathrm{supp}(\mu)$ satisfy
$\mathrm{dist}(z_{i},\partial Q_{\delta,\overline{\alpha}})<4$. Let $U$ be the
square $U=\\{x\in Q_{\delta,\overline{\alpha}}:\mathrm{dist}(x,\partial
Q_{\delta,\overline{\alpha}})\geq 4\\}$. Take $x\in\partial U$ satisfying
$|x-z_{i}|=\mathrm{dist}(z_{i},\partial U)$. Let $K$ be a closed square of
side-length $2R_{0}$ such that $x\in\partial K$ and $K\subset U$ (such a
square exists if $\delta$ is sufficiently small). By Step 3, there exists
$z_{j}\in\mathrm{supp}(\mu)\cap K$, $z_{j}\neq z_{i}$. Therefore

$|z_{i}-z_{j}|\leq|z_{i}-x|+|x-z_{j}|\leq\sqrt{32}+\mathrm{diam}(K)=\sqrt{32}+\sqrt{8}R_{0}.$
(72)

Without loss of generality can assume that $m_{i}<\overline{m}$ (otherwise
$m_{i}\geq\overline{m}>m_{\mathrm{b}}$ and there is nothing to prove). Let $T$
be the optimal transport map defining
$W_{2}(\mathbbm{1}_{Q_{\delta,\alpha}},\mu)$. Let $z\in T^{-1}(z_{i})$. By
Lemma 2.1 and Lemma 4.5(i),

$|z-z_{i}|+\frac{\overline{\alpha}}{1-\overline{\alpha}}c_{6}m_{i}^{\overline{\alpha}-1}\leq|z-z_{j}|+\frac{\overline{\alpha}}{1-\overline{\alpha}}c_{6}m_{j}^{\overline{\alpha}-1}.$
(73)

By Lemma 4.5(ii), $z_{i}\in T^{-1}(z_{i})$. Taking $z=z_{i}$ in (73) gives

$\frac{\overline{\alpha}}{1-\overline{\alpha}}c_{6}m_{i}^{\overline{\alpha}-1}\leq|z_{i}-z_{j}|+\frac{\overline{\alpha}}{1-\overline{\alpha}}c_{6}m_{j}^{\overline{\alpha}-1}\leq\sqrt{32}+\sqrt{8}R_{0}+\frac{\overline{\alpha}}{1-\overline{\alpha}}c_{6}\overline{m}^{\overline{\alpha}-1}$

by (72) and Lemma 4.15(i). Therefore

$m_{i}\geq\left[\frac{1-\overline{\alpha}}{c_{6}\overline{\alpha}}\left(\sqrt{32}+\sqrt{8}R_{0}+\frac{\overline{\alpha}}{1-\overline{\alpha}}c_{6}\overline{m}^{\overline{\alpha}-1}\right)\right]^{\frac{1}{\overline{\alpha}-1}}>1.5212\times
10^{-5}$

as required.

_Step 5: Proof of (iv)._ Take any $x\in T^{-1}(z_{i})$. Let $K$ be a closed
square of side-length $2R_{0}$ such that $x\in K$ and $K\subset
Q_{\delta,\overline{\alpha}}$ (such a square exists if $\delta$ is
sufficiently small). By Step 3, there exists at least one point
$z_{j}\in\mathrm{supp}(\mu)\cap K$. Therefore
$|x-z_{j}|^{2}\leq\mathrm{diam}(K)^{2}=8R_{0}^{2}$. By Lemma 2.1 and Lemma
4.5(i),

$|x-z_{i}|^{2}\leq|x-z_{j}|^{2}+\frac{\overline{\alpha}}{1-\overline{\alpha}}c_{6}m_{j}^{\overline{\alpha}-1}-\frac{\overline{\alpha}}{1-\overline{\alpha}}c_{6}m_{i}^{\overline{\alpha}-1}\leq
8R_{0}^{2}+\frac{\overline{\alpha}}{1-\overline{\alpha}}c_{6}m_{\mathrm{b}}^{\overline{\alpha}-1}.$

By Lemma 4.5(ii), $z_{i}\in T^{-1}(z_{i})$. Therefore

$\mathrm{diam}(T^{-1}(z_{i}))\leq 2\max_{x\in T^{-1}(z_{i})}|x-z_{i}|\leq
2\left(8R_{0}^{2}+\frac{\overline{\alpha}}{1-\overline{\alpha}}c_{6}m_{\mathrm{b}}^{\overline{\alpha}-1}\right)^{\frac{1}{2}}$

as required. ∎

The lower bound we obtained in Lemma 4.15(i) is good enough to ensure the
validity of the convexity inequality (50):

######  Corollary 4.16 (Convexity inequality).

Let
$\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}\in\mathcal{A}_{\delta,\overline{\alpha}}$
be a minimizer of $\mathcal{F}_{\delta,\overline{\alpha}}$. If $\delta>0$ is
sufficiently small and $\mathrm{dist}(z_{i},\partial
Q_{\delta,\overline{\alpha}})\geq 4$, then

$h_{\overline{\alpha}}(m_{i},n)\geq
0\quad\forall\;n\in\mathbb{N}\cap[3,\infty).$ (74)

###### Proof.

Recall that $\overline{m}=2.0620\times 10^{-4}$. By a direct computation we
see that

$\displaystyle h_{\overline{\alpha}}(\overline{m},3)>7\times 10^{-7}>0,\qquad
h_{\overline{\alpha}}(\overline{m},4)>8\times 10^{-4}>0,\qquad
h_{\overline{\alpha}}(\overline{m},5)>1\times 10^{-3}>0.$

Therefore (74) follows from Lemma 4.15(i), Lemma 4.11 and Corollary 4.12. ∎

###  4.4. Proof of Theorem 1.1

We are now in position to prove one of our main results.

######  Theorem 4.17 (Lower bound on $C_{\mathrm{p}}(\overline{\alpha})$).

We have

$C_{\mathrm{p}}(\overline{\alpha})\geq\frac{2-\overline{\alpha}}{1-\overline{\alpha}}\,c_{6}.$

Combining Theorem 4.17 with Lemma 4.1, Lemma 3.12 and Corollary 3.10 completes
the proof of Theorem 1.1.

###### Proof of Theorem 4.17.

By (48) it is sufficient to prove that

$\lim_{\delta\to
0}V^{-1}_{\delta,\overline{\alpha}}\min\left\\{\mathcal{F}_{\delta,\overline{\alpha}}(\mu):\mu\in\mathcal{A}_{\delta,\overline{\alpha}}\right\\}\geq\frac{2-\overline{\alpha}}{1-\overline{\alpha}}\,c_{6}.$
(75)

Let
$\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}\in\mathcal{A}_{\delta,\overline{\alpha}}$
be a minimizer of $\mathcal{F}_{\delta,\overline{\alpha}}$ and let

$\displaystyle\mathcal{I}$
$\displaystyle=\\{i\in\\{1,\ldots,N_{\mu}\\}:\mathrm{dist}(z_{i},\partial
Q_{\delta,\overline{\alpha}})\geq 4\\},$ (76) $\displaystyle\mathcal{J}$
$\displaystyle=\\{j\in\\{1,\ldots,N_{\mu}\\}:\mathrm{dist}(z_{j},\partial
Q_{\delta,\overline{\alpha}})<4\\}.$

Let $U$ be the tubular neighbourhood of $\partial
Q_{\delta,\overline{\alpha}}$ of width $4+D_{0}$, where $D_{0}$ was defined in
Lemma 4.15(v):

$U=\left\\{x+y:x\in\partial Q_{\delta,\overline{\alpha}},\;y\in
B_{4+D_{0}}(x)\right\\}\cap Q_{\delta,\overline{\alpha}}.$

Let $T$ be the optimal transport map defining
$W_{2}(\mathbbm{1}_{Q_{\delta,\overline{\alpha}}},\mu)$. By Lemma 4.15(v),

$\bigcup_{j\in\mathcal{J}}T^{-1}(z_{j})\subset U.$ (77)

Recall that $Q_{\delta,\overline{\alpha}}$ is a square of side-length
$V_{\delta,\overline{\alpha}}^{1/2}$. By Lemma 4.15(iv),
$|T^{-1}(z_{j})|>m_{\mathrm{b}}$ for all $j\in\mathcal{J}$. Therefore,  for
$\delta$ sufficiently small so that
$V_{\delta,\overline{\alpha}}^{1/2}>2(4+D_{0})$,

$\\#\mathcal{J}<\frac{|U|}{m_{\mathrm{b}}}=\frac{V_{\delta,\overline{\alpha}}-(V_{\delta,\overline{\alpha}}^{1/2}-2(4+D_{0}))^{2}}{m_{\mathrm{b}}}.$
(78)

Hence

$\lim_{\delta\to 0}\frac{\\#\mathcal{J}}{V_{\delta,\overline{\alpha}}}=0.$
(79)

Since
$\sum_{i=1}^{N_{\mu}}m_{i}=V_{\delta,{\color[rgb]{0,0,0}{\overline{\alpha}}}}$,
we have

$1\geq
V_{\delta,{\color[rgb]{0,0,0}{\overline{\alpha}}}}^{-1}\sum_{i\in\mathcal{I}}m_{i}=V_{\delta,{\color[rgb]{0,0,0}{\overline{\alpha}}}}^{-1}\sum_{i=1}^{N_{\mu}}m_{i}-V_{\delta,{\color[rgb]{0,0,0}{\overline{\alpha}}}}^{-1}\sum_{j\in\mathcal{J}}m_{j}\stackrel{{\scriptstyle\eqref{eq:Biden}}}{{\geq}}1-V_{\delta,{\color[rgb]{0,0,0}{\overline{\alpha}}}}^{-1}|U|.$

Using this and (78) we conclude that

$\lim_{\delta\to
0}V_{\delta,{\color[rgb]{0,0,0}{\overline{\alpha}}}}^{-1}\sum_{i\in\mathcal{I}}m_{i}=1.$
(80)

For $i\in\\{1\ldots,N_{\mu}\\}$, let $n_{i}$ be the number of edges of the
convex polygon $T^{-1}(z_{i})$. Recall from Lemma 2.6 that

$\sum_{i=1}^{N_{\mu}}(n_{i}-6)\leq 0.$ (81)

Finally, we put everything together to complete the proof:

$\displaystyle
V_{\delta,\overline{\alpha}}^{-1}\mathcal{F}_{\delta,\overline{\alpha}}(\mu)$
$\displaystyle\geq
V_{\delta,\overline{\alpha}}^{-1}\sum_{i=1}^{N_{\mu}}g_{\overline{\alpha}}(m_{i},n_{i})$
$\displaystyle(\textrm{equation }\eqref{eq:Putin})$ $\displaystyle\geq
V_{\delta,\overline{\alpha}}^{-1}\sum_{i\in\mathcal{I}}g_{\overline{\alpha}}(m_{i},n_{i})$
$\displaystyle\geq
V_{\delta,\overline{\alpha}}^{-1}\sum_{i\in\mathcal{I}}\left(g_{\overline{\alpha}}(1,6)+\nabla
g_{\overline{\alpha}}(1,6)\cdot(m_{i}-1,n_{i}-6)\right)$
$\displaystyle(\textrm{Corollary }\ref{Cor:CI})$
$\displaystyle=V_{\delta,\overline{\alpha}}^{-1}\sum_{i\in\mathcal{I}}\left(\frac{2-{\overline{\alpha}}}{1-{\overline{\alpha}}}\,c_{6}\,m_{i}+\kappa(n_{i}-6)\right)$
$\displaystyle(\textrm{equation }\eqref{eq:ineq})$
$\displaystyle=\frac{2-{\overline{\alpha}}}{1-{\overline{\alpha}}}\,c_{6}\,V_{\delta,\overline{\alpha}}^{-1}\sum_{i\in\mathcal{I}}m_{i}+V_{\delta,\overline{\alpha}}^{-1}\kappa\underbrace{\sum_{i=1}^{N_{\mu}}(n_{i}-6)}_{\leq
0\textrm{ by
}\eqref{eq:BNE}}-V_{\delta,\overline{\alpha}}^{-1}\sum_{j\in\mathcal{J}}\kappa(n_{j}-6)$
$\displaystyle\geq\frac{2-{\overline{\alpha}}}{1-{\overline{\alpha}}}\,c_{6}\,V_{\delta,\overline{\alpha}}^{-1}\sum_{i\in\mathcal{I}}m_{i}+3\kappa\,V_{\delta,\overline{\alpha}}^{-1}\\#\mathcal{J}.$
$\displaystyle(\kappa<0,\,n_{j}\geq 3)$

Taking the limit $\delta\to 0$ and using (79) and (80) proves (75), as
required. ∎

##  5\. The constrained optimal location problem: Proof of Theorem 1.2

This section is devoted to the proof of Theorem 1.2. The idea is to use
Theorem 1.1 together with the following relation between
$C_{\mathrm{c}}(\alpha)$ and $C_{\mathrm{p}}(\alpha)$:

######  Lemma 5.1 (Relation between the constrained and penalized problems).

For all  $\alpha\in(-\infty,1)$,

$C_{\mathrm{c}}(\alpha)\geq C_{\mathrm{p}}(\alpha)-\frac{c_{6}}{1-\alpha}.$
(82)

###### Proof.

By Remark 3.5,

$\displaystyle C_{\mathrm{c}}(\alpha)$
$\displaystyle=\lim_{L\to\infty}L^{\frac{1}{1-\alpha}}\inf\left\\{W^{2}_{2}(\mathbbm{1}_{Q},\mu):\mu\in\mathcal{P}_{\mathrm{d}}(Q),\;\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}\leq
L\right\\}$
$\displaystyle=\lim_{L\to\infty}L^{\frac{1}{1-\alpha}}\inf\left\\{W^{2}_{2}(\mathbbm{1}_{Q},\mu)+\frac{c_{6}}{1-\alpha}L^{\frac{\alpha-2}{1-\alpha}}\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}-\frac{c_{6}}{1-\alpha}L^{\frac{\alpha-2}{1-\alpha}}\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}\right.$
$\displaystyle\hskip
256.0748pt:\left.\mu\in\mathcal{P}_{\mathrm{d}}(Q),\;\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}\leq
L\right\\}$
$\displaystyle\geq\lim_{L\to\infty}L^{\frac{1}{1-\alpha}}\inf\left\\{W^{2}_{2}(\mathbbm{1}_{Q},\mu)+\frac{c_{6}}{1-\alpha}L^{\frac{\alpha-2}{1-\alpha}}\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}:\mu\in\mathcal{P}_{\mathrm{d}}(Q)\right\\}-\frac{c_{6}}{1-\alpha}L^{\frac{1}{1-\alpha}}L^{\frac{\alpha-2}{1-\alpha}}L$
$\displaystyle=\lim_{\delta\to
0}\left(\frac{c_{6}}{\delta(1-\alpha)}\right)^{\frac{1}{2-\alpha}}\inf\left\\{W^{2}_{2}(\mathbbm{1}_{Q},\mu)+\delta\sum_{i=1}^{N_{\mu}}m_{i}^{\alpha}:\mu\in\mathcal{P}_{\mathrm{d}}(Q)\right\\}-\frac{c_{6}}{1-\alpha}$
$\displaystyle=C_{\mathrm{p}}(\alpha)-\frac{c_{6}}{1-\alpha}$

by Remark 3.11. In the penultimate equality we used the change of variables
$\delta=\frac{c_{6}}{1-\alpha}L^{\frac{\alpha-2}{1-\alpha}}$. ∎

###### Proof of Theorem 1.2.

Let  $\alpha\in(-\infty,\overline{\alpha}]$. By Corollary 3.4, in order to
prove Theorem 1.2 it is sufficient to prove that
$C_{\mathrm{c}}(\alpha)=c_{6}$. We have

$\displaystyle c_{6}$ $\displaystyle=C_{\mathrm{c}}(0)$
$\displaystyle(\textrm{Remark }\ref{rem:Gdelta1})$ $\displaystyle\geq
C_{\mathrm{c}}(\alpha)$ $\displaystyle(C_{\mathrm{c}}(\alpha)\textrm{ is non-
increasing})$ $\displaystyle\geq
C_{\mathrm{p}}(\alpha)-\frac{c_{6}}{1-\alpha}$ $\displaystyle(\textrm{Lemma
}\ref{ref:RelCP})$ $\displaystyle=c_{6}$ $\displaystyle(\textrm{Theorem
}\ref{thm:pen})$

as required. ∎

##  6\. Paving the way towards $\alpha=1$

In this section we prove an asymptotic crystallization result for the full
range of  $\alpha\in(-\infty,1)$ under the ansatz (which we are not able to
prove) that the neighbouring cells of the smallest ones are not too large.

######  Theorem 6.1 (Asymptotic crystallization for all
${\color[rgb]{0,0,0}{\alpha\in(-\infty,1)}}$).

Let  $\alpha\in(-\infty,1)$ and $\delta>0$. Let
$\mu=\sum_{i=1}^{N_{\mu}}m_{i}\delta_{z_{i}}\in\mathcal{A}_{\delta,\alpha}$ be
a minimizer of $\mathcal{F}_{\delta,\alpha}$. Let
$i_{*}\in\\{1,\ldots,N_{\mu}\\}$ be the index of the smallest cell:
$m_{i_{*}}=\min_{i}m_{i}$ ($i_{*}$ need not be unique). Let $T$ be the optimal
transport map defining $W_{2}(\mathbbm{1}_{Q_{\delta,\alpha}},\mu)$. Assume
for all $\delta$ sufficiently small that the area of the ‘closest neighbour’
to the smallest cell is no more than $\tfrac{19}{4}$ times the area of the
smallest cell, i.e., $m_{j}\leq\frac{19}{4}m_{i_{*}}$ for all $j$ such that

$\mathrm{dist}(z_{i_{*}},\partial
T^{-1}(z_{i_{*}}))=\mathrm{dist}(z_{i_{*}},\partial
T^{-1}(z_{j}))=:d_{i_{*}j}.$

Assume also that, for all $\delta$ sufficiently small, $z_{i_{*}}$ is not too
close to the boundary:

$B_{d_{i_{*}j}}(z_{i_{*}})\subset Q_{\delta,\alpha}.$

Then the asymptotic crystallization results (13) and (14) hold.

First we prove an analogue of Lemma 4.11 for $\alpha$ close to $1$.

######  Lemma 6.2 (Positivity of $h_{\alpha}$ for $\alpha$ near $1$).

There exist s $\varepsilon>0$ such that, for all $\alpha\in(1-\varepsilon,1)$
and all integers $n\geq 3$, the following holds: if $h_{\alpha}(m_{1},n)\geq
0$ for some $m_{1}\geq 0$, then $h_{\alpha}(m,n)\geq 0$ for all $m\geq m_{1}$.

###### Proof.

Define $h_{1}:(0,\infty)\times[3,\infty)\to\mathbb{R}$ by

$h_{1}(m,n):=\lim_{\alpha\to 1}h_{\alpha}(m,n)=c_{n}m^{2}-c_{6}m-c_{6}m\ln
m-\kappa(n-6).$

_Step 1._ We claim that $h_{\alpha}$ converges to $h_{1}$ locally uniformly in
$m$ and uniformly in $n$ as $\alpha\to 1^{-}$. Let $m\in(0,\infty)$, $n\geq
3$, $\alpha\in(0,1)$. Then

$\frac{1}{c_{6}}(h_{\alpha}(m,n)-h_{1}(m,n))=\frac{m^{\alpha}-m+(1-\alpha)m\ln
m}{1-\alpha}=:\frac{\theta({\alpha})}{1-\alpha}.$

Observe that $\theta(1)=\theta^{\prime}(1)=0$ and
$\theta^{\prime\prime}(\alpha)=(\ln m)^{2}m^{\alpha}$. By Taylor’s Theorem,
there exists $\beta(\alpha)\in(\alpha,1)$ such that

$\frac{1}{c_{6}}|h_{\alpha}(m,n)-h_{1}(m,n)|=\frac{1}{2}(1-\alpha)|\theta^{\prime\prime}(\beta(\alpha))|=\frac{1}{2}(1-\alpha)(\ln
m)^{2}m^{\beta(\alpha)}.$

Fix $m_{1},m_{2}\in(0,\infty)$. Then

$\lim_{\alpha\to 1^{-}}\sup_{\begin{subarray}{c}m\in[m_{1},m_{2}]\\\
n\in[3,\infty)\end{subarray}}|h_{\alpha}(m,n)-h_{1}(m,n)|\leq\lim_{\alpha\to
1^{-}}\frac{c_{6}}{2}(1-\alpha)\sup_{m\in[m_{1},m_{2}]}(\ln
m)^{2}m^{\beta(\alpha)}=0$

as required.

_Step 2._ Next we study the shape of the function $m\mapsto h_{1}(m,n)$. Its
derivative is

$\partial_{m}h_{1}(m,n)=2c_{n}m-2c_{6}-c_{6}\ln m,$ (83)

which is strictly convex in $m$ with $\lim_{m\to
0}\partial_{m}h_{1}(m,n)=+\infty$,
$\lim_{m\to\infty}\partial_{m}h_{1}(m,n)=+\infty$. Therefore
$m\mapsto\partial_{m}h_{1}(m,n)$ has exactly one critical point, which is
$m=\frac{c_{6}}{2c_{n}}$. Since $n\mapsto c_{n}$ is decreasing,

$\partial_{m}h_{1}\left(\frac{c_{6}}{2c_{n}},n\right)=-c_{6}-c_{6}\ln\left(\frac{c_{6}}{2c_{n}}\right)\leq-
c_{6}-c_{6}\ln\left(\frac{c_{6}}{2c_{3}}\right)<-0.019<0.$

Therefore $m\mapsto h_{1}(m,n)$ has exactly two critical points, the smallest
critical point is a local maximum point, and the largest critical point is a
local minimum point. Let $\widetilde{m}(n)$ denote the local minimum point. By
the calculation above,

$\widetilde{m}(n)>\frac{c_{6}}{2c_{n}}>\frac{c_{6}}{2c_{3}}.$ (84)

Define $\varphi(n)$ to be the value of $h_{1}(\cdot,n)$ at its local minimum
point:

$\varphi(n):=h_{1}(\widetilde{m}(n),n).$

Observe that $\partial_{m}h_{1}(1,6)=0$. Therefore, by (84), the local minimum
point of $h_{1}$ is $\widetilde{m}(6)=1$ and $\varphi(6)=0$.

_Step 3._ We claim that there exists a constant $c>0$ such that $\varphi(n)>c$
for all integers $n\geq 3$, $n\neq 6$. First we show that it is sufficient to
prove this for the finite number of cases $n\in\\{3,4,5,7\\}$.

_Step 3a: Reduction to the case $n\in\\{3,4,5,7\\}$._ By equation (83), for
all $n\geq 3$,

$\partial_{m}h_{1}(1.05,n)=2c_{n}\cdot 1.05-2c_{6}-c_{6}\ln(1.05)\geq
2c_{\infty}\cdot 1.05-2c_{6}-c_{6}\ln(1.05)>0.005>0.$

Therefore

$\widetilde{m}(n)<1.05.$ (85)

For all $n\geq 7$,

$\displaystyle\partial_{n}\varphi(n)$ $\displaystyle=\frac{\partial
h_{1}}{\partial n}(\widetilde{m}(n),n)$ $\displaystyle(\textrm{since
}\partial_{m}h_{1}(\widetilde{m}(n),n)=0)$
$\displaystyle=\widetilde{m}^{2}(n)\,\partial_{n}c_{n}-\kappa$
$\displaystyle\geq\widetilde{m}^{2}(n)\,\partial_{n}c_{n}|_{n=7}-\kappa$
$\displaystyle(\textrm{by Lemma }\ref{lem:cn})$ $\displaystyle\geq
1.05^{2}\,\partial_{n}c_{n}|_{n=7}-\kappa$ $\displaystyle\textrm{(by
}\eqref{eq:mtildeLB})$ $\displaystyle>4\times 10^{-4}.$

Therefore $\varphi$ is increasing for $n\geq 7$. Consequently, for all
integers $n\geq 3$, $n\neq 6$,

$\varphi(n)\geq\min\\{\varphi(3),\varphi(4),\varphi(5),\varphi(7)\\}.$ (86)

_Step 3b: Proof for the case $n\in\\{3,4,5,7\\}$._ We show that the right-hand
side of (86) is positive. Let

$m_{1}(n):=\begin{cases}0.66&n=3,\\\ 0.92&n=4,\\\ 0.981&n=5,\\\
1.007&n=7,\end{cases}\quad\quad m_{2}(n):=\begin{cases}0.661&n=3,\\\
0.93&n=4,\\\ 0.982&n=5,\\\ 1.0075&n=7.\end{cases}$

Then evaluating $\partial_{m}h_{1}$ gives

$\partial_{m}h_{1}(m_{1}(n),n)\leq\begin{cases}-7\times 10^{-5}&n=3,\\\
-7\times 10^{-4}&n=4,\\\ -1\times 10^{-4}&n=5,\\\ -5\times
10^{-5}&n=7,\end{cases}\quad\quad\partial_{m}h_{1}(m_{2}(n),n)\geq\begin{cases}6\times
10^{-5}&n=3,\\\ 8\times 10^{-4}&n=4,\\\ 4\times 10^{-5}&n=5,\\\ 2\times
10^{-5}&n=7.\end{cases}$

Let $n\in\\{3,4,5,7\\}$. By the Intermediate Value Theorem, the map
$m\mapsto\partial h_{1}(m,n)$ has a root between $m_{1}(n)$ and $m_{2}(n)$.
Moreover, since $\partial_{m}h_{1}(m_{1}(n),n)<0$, we have bracketed the
largest root $\widetilde{m}(n)$: $m_{1}(n)<\widetilde{m}(n)<m_{2}(n)$.
Therefore

$\displaystyle\varphi(n)\geq c_{n}m_{1}(n)^{2}-c_{6}m_{2}(n)-c_{6}m_{2}(n)\ln
m_{2}(n)-\kappa(n-6)\geq\begin{cases}0.01&n=3,\\\ 9\times 10^{-4}&n=4,\\\
2\times 10^{-4}&n=5,\\\ 1\times 10^{-4}&n=7.\end{cases}$

Combining this with (86) proves that $\varphi(n)>c>0$ for all integers $n\geq
3$, $n\neq 6$.

_Step 4._ By Step 1 of the proof of Lemma 4.11, the function $m\mapsto
h_{\alpha}(m,n)$ has at most two critical points for all $\alpha\in(0,1)$,
$n\geq 3$. If it has less than two critical points, then Lemma 6.2 follows
immediately, so we just need to consider the case where it has exactly two
critical points. By Step 1 of the proof of Lemma 4.11, the smallest critical
point is a local maximum point and the largest critical point is a local
minimum point.

By Step 1, $h_{\alpha}$ converges to $h_{1}$ uniformly on the interval
$[c_{6}/(2c_{3}),1.05]\times[3,\infty)$. Observe that the local minimum point
$\widetilde{m}(n)$ of $m\mapsto h_{1}(m,n)$ lies in the interval
$[c_{6}/(2c_{3}),1.05]$ by (84) and (85). Let $n$ be an integer, $n\geq 3$,
$n\neq 6$. By Step 3, $h_{1}(\widetilde{m}(n),n)>c>0$. Therefore, for $\alpha$
sufficiently close to 1, the value of $m\mapsto h_{\alpha}(m,n)$ at its local
minimum point is also positive by the uniform convergence. This proves Lemma
6.2 for the case $n\geq 3$, $n\neq 6$.

Finally, the case $n=6$ follows immediately from Step 2 of the proof of Lemma
4.11, where it was shown that the value of $h_{\alpha}(m,6)$ at its local
minimum point is $0$ for all $\alpha\in(0,1)$. ∎

An immediate consequence of Lemma 6.2 is the following convexity inequality:

######  Corollary 6.3 (Reduction to $n\in\\{3,4,5\\}$).

Let $n\geq 6$ be an integer. If $\alpha\in(0,1)$ is sufficiently close to $1$,
then $h_{\alpha}(m,n)\geq 0$ for all $m\geq 0$.

###### Proof.

Observe that $h_{\alpha}(0,n)=-\kappa(n-6)\geq 0$ for all $n\geq 6$. Therefore
the result follows immediately from Lemma 6.2. ∎

Now we are in a position to prove the main theorem of the section.

###### Proof of Theorem 6.1.

By the monotonicity result (Lemma 3.12) we can assume that $\alpha\in(0,1)$.
Let $\mu$ and $z_{i_{*}}$ be as in the statement of Theorem 6.1. To simplify
the notation, let $\overline{z}=z_{i_{*}}$,
$m=\mu(\\{\overline{z}\\})=\min\\{\mu(\\{z\\}):z\in\mathrm{supp}(\mu)\\}$. Let
$z\in\mathrm{supp}(\mu)$ satisfy

$\mathrm{dist}(\overline{z},\partial
T^{-1}(\overline{z}))=\mathrm{dist}(\overline{z},\partial T^{-1}(z))=:d.$

Let $x$ belong to the edge
$e_{\overline{z}z}:=\overline{T^{-1}(\overline{z})}\cap\overline{T^{-1}(z)}$
and let $x$ satisfy $|\overline{z}-x|=d$, which means that $x$ is the closet
point on the boundary of the Laguerre cell $\overline{T^{-1}(\overline{z})}$
to $\overline{z}$. Define $M=\mu(z)$. By assumption, $M\leq\frac{19}{4}m$.

_Step 1: Upper bound on $|\overline{z}-z|$._ The point $x$ lies in the edge
$e_{\overline{z}z}$. Therefore by Lemma 2.1 and Lemma 4.5(i) we have

$|x-\overline{z}|^{2}+\frac{\alpha}{1-\alpha}c_{6}m^{\alpha-1}=|x-z|^{2}+\frac{\alpha}{1-\alpha}c_{6}M^{\alpha-1}.$

Moreover, $x=\overline{z}+t(z-\overline{z})$ for some $t\in(0,1)$ (since $x$
is the closest point to $\overline{z}$ in the edge $e_{\overline{z}z}$, which
has normal $z-\overline{z}$). Solving for $t$ gives

$x-\overline{z}=\left[\frac{1}{2}+\frac{c_{6}}{2}\frac{\alpha}{1-\alpha}\frac{M^{\alpha-1}-m^{\alpha-1}}{|\overline{z}-z|^{2}}\right](z-\overline{z}).$

The term in square brackets is positive since $\overline{z}$ lies in its
Laguerre cell $\overline{T^{-1}(\overline{z})}$ (Lemma 4.5(ii)). Moreover, the
ball $B_{d}(\overline{z})$ is contained in the Laguerre cell
$\overline{T^{-1}(\overline{z})}$ (since $e_{\overline{z}z}$ is the closest
edge to $\overline{z}$). Therefore

$\pi d^{2}\leq
m\quad\Longleftrightarrow\quad\pi\left[\frac{1}{2}+\frac{c_{6}}{2}\frac{\alpha}{1-\alpha}\frac{M^{\alpha-1}-m^{\alpha-1}}{|\overline{z}-z|^{2}}\right]^{2}|z-\overline{z}|^{2}\leq
m{\color[rgb]{0,0,0}{.}}$

Let $R=|z-\overline{z}|$. Then we can rewrite the inequality above as

$R^{2}-2\left(\frac{m}{\pi}\right)^{\frac{1}{2}}R+c_{6}\frac{\alpha}{1-\alpha}(M^{\alpha-1}-m^{\alpha-1})\leq
0.$

Thus we get the upper bound

$R\leq\left(\frac{m}{\pi}\right)^{\frac{1}{2}}+\left(\frac{m}{\pi}-c_{6}\frac{\alpha}{1-\alpha}(M^{\alpha-1}-m^{\alpha-1})\right)^{\frac{1}{2}}.$
(87)

_Step 2: Lower bound on $m$._ Let $\mathcal{C}^{\mu}$ be the partition
associated to the minimizer $\mu$. Define a new partition $\mathcal{D}$ by
replacing the cells $\overline{T^{-1}(\bar{z})}$ and $\overline{T^{-1}(z)}$
with their union. By Lemma 4.14

$\displaystyle 0$ $\displaystyle\leq
F(\mathcal{D})-F(\mathcal{C}^{\mu})\leq\frac{c_{6}}{1-\alpha}\left((m+M)^{\alpha}-m^{\alpha}-M^{\alpha}\right)+\frac{mM}{m+M}|\bar{z}-z|^{2}.$

By Young’s inequality $(a+b)^{2}\leq 2(a^{2}+b^{2})$ and (87) we obtain

$\displaystyle 0$
$\displaystyle\leq\frac{c_{6}}{1-\alpha}\left((m+M)^{\alpha}-m^{\alpha}-M^{\alpha}\right)+2\frac{mM}{m+M}\left[\frac{2}{\pi}m-c_{6}\frac{\alpha}{1-\alpha}(M^{\alpha-1}-m^{\alpha-1})\right]$
$\displaystyle=\frac{c_{6}}{1-\alpha}M^{\alpha}\left(\left(\frac{m}{M}+1\right)^{\alpha}-\left(\frac{m}{M}\right)^{\alpha}-1\right)+2\frac{1}{\frac{m}{M}+1}m^{\alpha}\left[\frac{2}{\pi}m^{2-\alpha}-c_{6}\frac{\alpha}{1-\alpha}\left(\left(\frac{M}{m}\right)^{\alpha-1}-1\right)\right].$

Define $\lambda:=\frac{m}{M}$. By assumption, $\lambda\in[\frac{4}{19},1]$.
Then rearranging the previous inequality gives the lower bound