Least square assignment and hyperplanes

Question

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.

Answer 1

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.