Weighted area of a Voronoi cell - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T19:22:37Z http://mathoverflow.net/feeds/question/78103 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/78103/weighted-area-of-a-voronoi-cell Weighted area of a Voronoi cell Joord Jacobsen 2011-10-14T06:37:43Z 2011-10-14T13:08:01Z <p>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</p> <p>$V_i = {x\in S: \|x - x_i\|^2 + w_i \leq \|x - x_j\|^2 + w_j \forall j \neq i }$</p> <p>i.e. a "weighted Voronoi diagram". Now let's consider varying the weight $w_1$ while fixing the other weights; specifically, consider the function</p> <p>$f(w_1) = w_1\cdot \text{Area}(V_1)$</p> <p>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 </p> <p>$V_i = {x\in S: \|x - x_i\| + w_i \leq \|x - x_j\| + w_j \forall j \neq i }$ ?</p> http://mathoverflow.net/questions/78103/weighted-area-of-a-voronoi-cell/78130#78130 Answer by Joseph O'Rourke for Weighted area of a Voronoi cell Joseph O'Rourke 2011-10-14T13:08:01Z 2011-10-14T13:08:01Z <p>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, <a href="http://tintoretto.ucsd.edu/andrew/voronoi.html" rel="nofollow">this Matlab code</a> written by Andrew Kwok, which produced the image below (left), or <a href="http://www.nirarebakun.com/voro/emwvoro.html" rel="nofollow">this Java and VB code</a> by Takashi Ohyama, or <a href="http://web.informatik.uni-bonn.de/I/GeomLab/VoroAdd/index.html.en" rel="nofollow">this applet</a> 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. <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/PowerDiagram.jpg"/> &nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/PowerDiag2.jpg"/> <br /></p>