Should coffee machines be placed at the region's boundary?

Question

This is a continuation of Should coffee machines be deconcentrated?

Recall that some region is denoted by convex and compact $E\subset \mathbb R^2$. $N\ge 1$ coffee machines are provided for the people living on $E$, of capacities $\alpha_1,\ldots, \alpha_N>0$. Assume the population of $E$ is uniformly distributed such that

$$\sum_{n=1}^N \alpha_n = \ell(E),$$

where $\ell$ is the Lebesgue measure. If locating the machines at $x_1,\ldots, x_N\in E$ with $X:=(x_1,\ldots, x_N)$, the transportation cost is given as

$$F(X):=W_2(\mu_X,\ell) \quad\mbox{with}\quad \mu_X:=\sum_{n=1}^N \alpha_n\delta_{x_n}, \quad\quad \forall X\in E^N,$$

where $W_2$ denotes the Wasserstein metric of order $2$. As $F:E^N\to\mathbb R_+$ is Lipschitz and $E^N$ is compact, its minimum is attained. Can we find a minimiser $X^*=(x_1^*,\ldots, x_N^*)\in E^N$ belonging to the interior of $E^N$? Namely $x_n^* \notin \partial E$ for all $n=1,\ldots, N$.

Answer 1

$\newcommand{\ga}{\gamma}\newcommand{\Ga}{\Gamma}\newcommand{\al}{\alpha}\newcommand{\p}{\partial}\newcommand{\de}{\delta}$Without loss of generality (wlog), $\ell$ is the uniform probability distribution over $E$ and hence $\sum_{i=1}^N\al_i=1$. Here it is assumed that the interior $E^\circ$ of $E$ is nonempty.

Let $\Ga$ be the set of all probability distributions $\ga$ over $E\times E$ such that for some $(x_1,\dots,x_N)\in E^N$ the marginals of $\ga$ are $\sum_{i\in[N]}\al_i\de_{x_i}$ and $\ell$, where $[N]:=\{1,\dots,N\}$. Informally, $\ga(X\times A)$ is the mass transported from a set $X$ to a set $A$ under the plan $\ga$.

Let $\ga^*\in\Ga$ with marginals $\sum_{i\in[N]}\al_i\de_{x_i^*}$ and $\ell$ be an optimal transportation plan in the sense that \begin{equation*} C(\ga):=\int_E|x-y|^2\,\ga(dx\times dy)\ge C(\ga^*) \end{equation*} for all $\ga\in\Ga$, where $|\cdot|$ is the Euclidean norm.

Claim: $x_i^*\in E^\circ$ for all $i\in[N]$.

Proof: Suppose the contrary. Then wlog $x_1^*\in\p E$. So, wlog $x_1^*=(0,0)$ and $(s,t)\in E$ implies $s\le0$ -- that is, the first coordinate of any point in $E$ is $\le0$. Let \begin{equation*} \ga_i^*(A):=\ga^*(\{x_i^*\}\times A) \end{equation*} for all Borel subsets $A$ of $E$. To simplify writing, suppose that the $x_i^*$'s are pairwise distinct. Then \begin{equation*} C(\ga^*)=\sum_{i\in[N]}\int_E|x_i^*-y|^2\,\ga_i^*(dy). \end{equation*} (Otherwise, first rewrite $\sum_{i\in[N]}\al_i\de_{x_i}$ as $\sum_{i\in[n]}\beta_j\de_{z_j}$ with pairwise distinct $z_j$'s and appropriate $n$ and $\beta_j$'s.) Also, $\ga_1^*(\p E)\le\ga^*(\{x_1^*,\dots,x_N^*\}\times\p E)=\ell(\p E)=0$ and hence $$\ga_1^*(E^\circ)=\ga_1^*(E)-\ga_1^*(\p E)=\ga_1^*(E)=\al_1>0.$$ Therefore and because the first coordinate of any point in $E$ is $\le0$, the first coordinate of the barycenter $\bar x_1^*$ of the measure $\ga_1^*$ is $<0$. So, $\bar x_1^*\ne(0,0)=x_1^*$. Also, $\bar x_1^*\in E$, since $E$ is convex. Moreover, it is easy to see (say, by differentiation) that $\bar x_1^*$ is the unique minimizer of $\int_E|x-y|^2\,\ga_1^*(dy)$ over $x\in E$.

It follows that \begin{equation*} C(\bar\ga^*)<C(\ga^*), \tag{3}\label{3} \end{equation*} where $\bar\ga^*\in\Ga$ is defined by the conditions \begin{equation*} \bar\ga^*(\{x_i^*\}\times A)=\ga^*(\{x_i^*\}\times A) \quad\text{if }i\in\{2,\dots,N\}, \end{equation*} \begin{equation*} \bar\ga^*(\{\bar x_1^*\}\times A)=\ga^*(\{x_1^*\}\times A) \end{equation*} for all Borel $A\subseteq E$.

Inequality \eqref{3} contradicts the optimality of $\ga^*$. $\quad\Box$

Answer 2

The minimizers cannot lie on the boundary. In fact, denote by $E_i \subset E$ the set of all points which are transported to $x_i^*$. Then, $x_i^*$ has to be the center of mass of $E_i$ and, thus, cannot lie on the boundary. I would also like to mention that this problem is well understood, see, e.g., http://doi.org/10.1137/141000993 and the references therein.