Weighted area of a Voronoi cell

2011-10-14T06:37:43Z

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$, where

$V_i = {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". Now let's consider varying the weight $w_1$ while fixing the other weights; specifically, consider the function

$f(w_1) = w_1\cdot \text{Area}(V_1)$

Clearly as $w_1 \rightarrow 0$ we have $f(w_1) \rightarrow 0$ and as $w_1 \rightarrow \infty$ we have $f(w_1) \rightarrow 0$ as well. My question: is $f(w_1)$ unimodal? Convex? Is the answer different if I only have $n=2$ points? What if I define my cells slightly differently, such as

$V_i = {x\in S: \|x - x_i\| + w_i \leq \|x - x_j\| + w_j \forall j \neq i }$ ?

Answer by Joseph O'Rourke for Weighted area of a Voronoi cell

2011-10-14T13:08:01Z

This is not an answer, just a way to empirically explore your question. There is publicly available code for computing the weighted Voronoi diagram. For example, this Matlab code written by Andrew Kwok, which produced the image below (left), or this Java and VB code by Takashi Ohyama, or this applet by Oliver Münch, which produced the image below (right). Using such code, it would not be too difficult to gather data to plot $f(w_1)$ in a random diagram and see if it is unimodal or convex.

Weighted area of a Voronoi cell - MathOverflow

Weighted area of a Voronoi cell

Answer by Joseph O'Rourke for Weighted area of a Voronoi cell