## Weighted area of a Voronoi cell

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

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

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9333946704864502, "perplexity_flag": "head"}