This question is related to the earlier question [Weighted area of a Voronoi cell](https://mathoverflow.net/questions/78103/weighted-area-of-a-voronoi-cell) . As in that question, let $X = \{ x\_1,\dots,x\_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w\_1,\dots,w\_n\}$ denote a set of weights corresponding to the $n$ points in $X$. Define the "power diagram" of $X$ in $S$ to be a partition of $S$ into at most $n$ pieces $V\_i(\mathbf{w})$, where


$V\_i(\mathbf{w}) = \{x\in S: \|x - x\_i\|^2 + w\_i \leq \|x - x\_j\|^2 + w\_j \forall j \neq i \}$


i.e. a "weighted Voronoi diagram". Thus, larger values of $w\_i$ correspond to smaller cells $V\_i$. The cells are always convex, and the partition does not change if we add a constant to all terms of a weight vector $\mathbf{w}$.


My question is: let's consider some quantity $Q(V\_i(\mathbf{w}))$ associated with the Voronoi cells with the following monotonicity property: for any two weight vectors $\mathbf{w}$ and $\mathbf{w}'$, if it turns out that $V\_i(\mathbf{w})\subsetneq V\_i(\mathbf{w}')$, then $Q(V\_i(\mathbf{w})) < Q(V\_i(\mathbf{w}'))$. Examples of $Q$ would be the area, perimeter, diameter, or width of the cells. I want to know: is it always the case that $Q(V\_i(\mathbf{w}))$ is somehow "equivalent" to the gradient of some other function?


My reasoning for this question is as follows: let's say we want to select weights $\mathbf{w}$ such that $Q(V\_i(\mathbf{w}))$ is equal for all $i$. This means that we want to *increase*(resp. decrease) values of $w\_i$ for those regions where $Q(V\_i(\mathbf{w}))$ is large (resp. small). A sensible way to do this would be to iteratively set $w\_i \mapsto w\_i + \epsilon Q(V\_i(\mathbf{w})) $, where $\epsilon$ is some tiny stepsize. I have tried numerical experiments with this scheme for the case where $Q$ measures area or perimeter and this seems to work.



Choosing the weights of a Voronoi diagram -- is this function always the gradient of another function?
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](https://mathoverflow.net/q/67318/39495). 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).](http://page.mi.fu-berlin.de/rote/Papers/abstract/Optimally+solving+a+transportation+problem+using+Voronoi+diagrams.html)
> 
> 
> 


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


