Skip to main content
3 of 3
replaced http://mathoverflow.net/ with https://mathoverflow.net/

Looking at the last paragraph of your question, it might seem reasonable to reformulate the question as: can we always select weights $\mathbf{w}$, such that the values $Q(V_i(\mathbf{w}))$ satisfy prescribed ratios: if we normalize by the sum of all entries $$s(\mathbf{w}):=\sum_{i=1}^nQ(V_i(\mathbf{w}))$$ we get a vector $$Q_{\text{norm}}(\mathbf{w}):=\frac{1}{s(\mathbf{w})}(Q(V_i(\mathbf{w})))_{1\leq i\leq n}$$ which is contained in the simplex $\Delta_{n-1}=\{(x_i)_{1\leq i\leq n}|\sum_i=1\}$. Then the question is: can we find for every point $p\in\Delta_{n-1}$ weights $\mathbf{w}$ such that $Q_{\text{norm}}=p$. For example if we take $p$ to be the barycenter of $\Delta_{n-1}$, then we would want to select weights such that $Q(V_i(\mathbf{w}))$ are equal for all $i$.

I can answer this question completely under the additional assumption that $Q$ is continuous. (Your examples "area, perimeter, diameter, or width of the cells" are all continous). What we need to prove is the surjectivity of the continous map $$Q_{\text{norm}}\colon\, \mathbb{R}^n\to \Delta_{n-1}.$$ We consider a map $$\begin{align}f\colon\, \Delta_{n-1}&\to\mathbb{R}^n\\x=(x_1,\dots,x_n)&\mapsto f(x)=(\log(x_1),\dots,\log(x_n)).\end{align}$$ This is only defined on the interior of $\Delta_{n-1}$, but we extend the definition on the boundary $\partial\Delta_{n-1}$ by setting $\log(0)=-\infty$. Also we extend the definition of the Voronoi diagram to allow some (but not all) components of the weight vector to be $-\infty$; the coresponding Voronoi regions will be empty. These definitions then allow us to compose $f$ with $Q_{\text{norm}}$ to get the map $$Q_{\text{norm}}\circ f\colon\, \Delta_{n-1}\to\Delta_{n-1},$$ which is continous and has the nice properties to map faces to faces: If some coordinates of $x$ are zero, the corresponding coordinates in $f(x)$ are $-\infty$ and the corresponding coordinates in $Q_{\text{norm}}\circ f(x)$ are also zero, since the corresponding Voronoi regions are empty. Therefore a face of $\Delta_{n−1}$ is mapped to itself.

Then we can apply a little (but often useful) lemma from algebraic topology that just states that such a map must be surjective. See for this question (an the answers): Map from simplex to itself that preserves sub-simplices. Hence $Q_{\text{norm}}\circ f$ is surjective and therefore also $Q_{\text{norm}}$ is surjective, which is what we wanted to show.

Edit: If $Q$ is taken to be the area and you are looking for an all equal area partition, then this partition is even unique up to sets of measure zero. A nice proof of this geometrical proof is given in the following paper, where they also consider some generalizations of the question:

Darius Geiß, Rolf Klein, Rainer Penninger, and Günter Rote, Optimally solving a transportation problem using Voronoi diagrams, Computational Geometry, Theory and Applications 46 (2013), 1009–1016, special issue for the 28th European Workshop on Computational Geometry (EuroCG'12).

(It is not the first proof of this results, see the references of this paper.)

Moritz Firsching
  • 10.7k
  • 3
  • 63
  • 88