Choosing the weights of a Voronoi diagram -- is this function always the gradient of another function?

Question

This question is related to the earlier question 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.

Answer 1

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.)