4

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 }$ ?

flag
Good question. The second definition is quite different from the first, and much worse understood. – Igor Rivin Oct 14 2011 at 10:24

1 Answer

1

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.
                

link|flag

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.