Consider the setup of the [$k$-means problem](https://en.wikipedia.org/wiki/K-means_clustering) and assume that the data points are confined to $k$ balls of radius $\varepsilon$ while the pairwise distances between the centers of the balls are $> 2 \varepsilon$, and each ball contains the same number of points. It seems to me that it should be possible to show that the solution of the $k$-means problem puts all the centers in these balls, exactly one per each ball (in which case it is clear that each center will be the mean of the points in the corresponding ball). I have trouble showing this, but I feel that this has to be known. Any reference? or am I missing some additional necessary condition?


More precise statement: Let $B\_2$ be the unit $\ell\_2$ ball in $\mathbb R^d$ and consider datapoints $\{x\_i, i=1,\dots,n\} \subset \mathbb R^d$ and (true) centers $\{v\_1,\dots,v\_k\} \subset \mathbb R^d$ such that


* for each $i$, $x\_i \in v\_j + \varepsilon B\_2$ for some $j \in [k]$, and
* $\|v\_j - v\_\ell\|\_2 > 2\varepsilon$ for all $j \neq \ell$, and
* $|\{i:\; x\_i \in v\_j + \varepsilon B\_2\}|$ is the same for all $j \in [k]$.


Let $\{v^\*\_1,\dots,v^\*\_k\}$ be an optimal solution to the k-means problem. We would like to show that $v^\*\_j \in v\_{\pi(j)} + \varepsilon B\_2$ for all $j \in [k]$ and some permutation $\pi : [k] \to [k]$. 


(It would be nice if this can be extended to constant-factor approximate solutions of the k-means problem.)




---


Alternative formulation in terms of measure approximation (see [Pollard 82](http://www.stat.yale.edu/~pollard/Papers/Pollard82ITT.pdf)): Let $\mu$ be a measure on $\mathbb R^d$ supported on a collection $S\_1,\dots,S\_k$ of disjoint sets. Let $\mathcal P\_k$ be the collection of discrete measures on $\mathbb R^d$ with at most $k$ atoms (objects of the form $\sum\_{j=1}^k \pi\_j \,\delta\_{v\_j}$).


Assume that 


* Diameter of $S\_j < 2\varepsilon$, for all $j$.
* $S\_j$ and $S\_\ell$ are suitably separated (?) relative to $\varepsilon$.
* $\mu(S\_j)$ are equal for all $j \in [k]$.


Let $\mu^\*\_k$ be a solution of $\min\_{\nu \in \mathcal P\_k} W\_2(\mu,\nu)$ where $W\_2$ is the $2$-Wasserstein distance. Then $\mu^\*\_k$ will have exactly $k$ atoms one within each $S\_j, j \in [k]$.



Solution of the k-means problem in a simple case
There are counterexamples in $\mathbb{R}^2$ under these conditions.


For $(d,k,n) = (2,2,4)$, place the balls such that they fit (neighborhoods of) the corners of a square. Here's such a configuration, with the K-means solution $(\theta\_1,\theta\_2)$ outside of the balls:
[Image.](https://i.stack.imgur.com/ZQvvP.png)


Similarly, placing two balls at (center) distance $2+\delta$ (wlog $\varepsilon=1$) with $M$ and $m$ points in each ball as close to the other ball as possible and the remaining $M-m$ diametrically opposite has two (plausible) K-means assignments, at total cost $\frac{\delta^2}{4}(m+M)$ vs $M$. The first assignment places a center between (outside) the two balls and is optimal for $\delta \leq 2$ and sufficiently large $M$.


More restrictive bounds on the center distances, e.g. $\|v\_j - v\_\ell\|\_2>4$, might work. It dismisses my counterexamples and has had some success when proving correctness of algorithms for K-means.


$\|v\_j - v\_\ell\|\_2>4$ mentioned here:


<https://arxiv.org/abs/1408.4045>


https ://arxiv.org/abs/1309.3256


A different approach to restricting ball proximity is used here:


https ://arxiv.org/abs/1004.1823


