Let $S$ be a finite set of points in $\mathbb{R}^{d}$, $c(s) \in [0,1]$ such that $\sum\_{s \in S} c(s) = 1$, $\rho$ continuous and non-vanishing probability distribution on $[0,1]^{d}$ and $\mu $ measure with respect to $\rho$, i.e. $ \mu (X) = \int\_{X} \rho (x) \ dx$. Let us suppose that there exists an assignment $ \text{L} \colon [0,1]^d \to S$ such that it minimizes


$$ \int\_{ [0,1]^{d} } \rho (x) \ \delta^2 (x, \text{L} (x)) \ d x $$


over all possible assignments that satisfy $ \mu ( \text{L}^{-1} (s) ) = c(s)$ for all $s \in S$, where $\delta$ is the Euclidean distance in $\mathbb{R}^{d}$.


I would like to prove that for all $s,t \in S, \ s \not = t$ there exists a hyperplane $\alpha$ orthogonal to $(t-s)$ such that $ \mu ( \alpha\_{ts} \cap \text{L}^{-1} (s) ) = 0 $ and $ \mu ( \alpha\_{st} \cap \text{L}^{-1} (t)) = 0 $, where $ \alpha\_{ts}$ is the half-space bounded by $\alpha$ and containing $\alpha + (t-s)$, and $\alpha\_{st}$ is the complementary half-space.


At first, I considered proving this constructively by describing the hyperplane, but since I don't know how this assignment looks like, I think this could be proven by contradiction. So, let us assume that for all hyperplanes orthogonal to $(t-s)$ it holds: $ \mu ( \alpha\_{ts} \cap \text{L}^{-1} (s) ) >0 $ or $\mu ( \alpha\_{st} \cap \text{L}^{-1} (t)) >0 $. In case, where both $ \mu ( \alpha\_{ts} \cap \text{L}^{-1} (s) ) >0 $ or $\mu ( \alpha\_{st} \cap \text{L}^{-1} (t)) >0 $, we can simply rearrange points that are not assigned efficiently and get better assignment, which is a contradiction.


However, I don't know how to prove it in case, where only one of the measures is positive. I would appreciate any advice.



Least square assignment and hyperplanes
There is always a minimizing assignment with this hyperplane property. So if the minimizing assignment is unique, then the hyperplane property always holds.


It is enough to show that $L^{-1}(s)$ and $L^{-1}(t)$ can always be replaced by regions which are divided by an appropriate hyperplane and which do not increase the average squared distance.


So let $U$ and $V$ be the result of cutting $L^{-1}(s) \cup L^{-1}(t)$ by some hyperplane orthogonal to $s-t$ such that $\mu(U)=c(s)$ and $\mu(V)=c(t)$, with $s$ and $t$ on the right sides of the hyperplane as described in the question. It is enough to show that


$$\int\_{U}|x-s|^2 d\mu + \int\_{V}|x-t|^2 d\mu \le
\int\_{L^{-1}(s)}|x-s|^2 d\mu + \int\_{L^{-1}(t)}|x-t|^2 d\mu$$ ​
By expanding $|x-s|^2$ into $x.x-2s.x+s.s$, subtracting out $c(s)s.s$ on both sides, expanding $|x-t|^2$ into $x.x-2t.x+t.t$, subtracting out $c(t)t.t$ on both sides, and then removing the integrals of $x.x$ which are over the same regions, this is equivalent to


$$\int\_{U}-2s.x\, d\mu + \int\_{V}-2t.x\, d\mu \le
\int\_{L^{-1}(s)}-2s.x\, d\mu + \int\_{L^{-1}(t)}-2t.x\, d\mu$$


After removing the factor of $-2$ and removing the intersections $U\cap L^{-1}(s)$ and $V\cap L^{-1}(t)$, this is equivalent to
$$\int\_{L^{-1}(s)-U}s.x\, d\mu + \int\_{L^{-1}(t)-V}t.x\, d\mu \le
\int\_{U-L^{-1}(s)}s.x\, d\mu + \int\_{V-L^{-1}(t)}t.x\, d\mu$$


Since $L^{-1}(s)-U=V-L^{-1}(t)$, this is equivalent to
$$\int\_{L^{-1}(s)-U}(s-t).x\, d\mu \le
\int\_{U-L^{-1}(s)}(s-t).x\, d\mu$$


Since the hyperplane dividing $U$ and $V$ is of the form $x.(s-t)=h$ for some $h$, these are integrals over regions of equal $\mu$-measure, where the left integrand is $\le h$ and the right integrand is $\ge h$. So the inequality holds, QED.


