Weighted area of a Voronoi cell

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

Let me answer at least some of your questions. I will only talk about your first definition of the cells, since these are somewhat nicer, as Igor Rivin pointed out.

You consider the function $f(w_1)=w_1\cdot\text{Area}(w_1)$ and asked whether it is convex. I assume you mean "Is the set $\{(x,f(x)):f(x)\geq 0\}\subset\mathbb{R}^2$ convex?", or in other words: "Is the function $f$ concave on the interval where it is positive?" I will first show that the answer to that question is "no, not in general".

Let $p\in \mathbb{R}$ be the number where the region associated to the first weight in the diagram with $w_1=p$ is a single point and let $z\in \mathbb{R}$ be the biggest number such that $\text{Area}(z)=1$. So in general $$\text{Area}(w_1)=\begin{cases}1&w_1\leq z\\\text{interesting}&z\leq w_1\leq p\\0&p\leq w_1\end{cases}$$ Choose the first point as $(\frac{1}{2},\frac{1}{2})$ and four more arranged in a square around it: $(\frac{1}{4},\frac{1}{2}),(\frac{1}{2},\frac{1}{4}),(\frac{3}{4},\frac{1}{2}),(\frac{1}{2},\frac{3}{4})$ and choose all weights equal to some number $c\in\mathbb{R}$. In this case $$\text{Area}(w_1)=\begin{cases}1&w_1\leq z\\(w_1-p)^2&z\leq w_1\leq p\\0&p\leq w_1\end{cases}$$ Here $z$ and $p$ depend on $c$, but we choose $c$ such that $0\leq z<p$. Then $f(w_1)=w_1\cdot\text{Area}(w_1)$ on the interval is $[z,p]$ is the cubic $w_1\cdot(w_1-p)^2$ near $p$ and in fact not concave near $p$.

This behavior is somewhat typical. Let me illustrate it with a bit more interesting example. We give a "random diagram" as suggested by Joseph O'Rourke. I obtained the following pictures with sage.

A gif with more steps (1.7M)

The white region is the one associated with $w_1$. Here is a plot of the corresponding function $f(w_1)$:

Lets zoom in on the non-concave part:

Let us explore the function $\text{Area}(w_1)$ a bit more in general. To find the power diagram we can use the convex hull method (for example described in Jiří Matoušek, Lectures on Discrete Geometry, p. 118 (Ch. 5.7)). Roughly speaking, to each of the given points in $\mathbb{R}^2$ we associate a hyperplane tangent to the paraboloid in $\mathbb{R}^3$ and lift it up and down with the weights to obtain a polyhedron. The projection of this polyhedron on $\mathbb{R}^2$ gives the power diagram. We can intersect this polyhedron with the infinite prism over the unit square to obtain a new polyhedron $P$. Without loss of generality, we assume that the paraboloid is based at the first point with weight $w_1$. Hence the hyperplane associated to this point is parallel to $\mathbb{R}^2\subset\mathbb{R}^3$. Then $\text{Area}(w_1)$ is the area which this hyperplane cuts off the polyhedron $P$. It is somewhat understood how those cuts behave. By Brunn's slice inequality (see for example the same book by Matoušek, Thm 12.2.1, p. 297) we get

1. $\text{Area}(w_1)$ is monotonically decreasing
2. $\sqrt{\text{Area}(w_1)}$ is concave on [z,p].

So maybe it would be interesting to ask whether $w_1\cdot\sqrt{\text{Area}(w_1)}$ is concave or unimodal. But I don't quite see the point why one should multiply $w_1$ with $\text{Area}(w_1)$ in the first place, since it somewhat obscures the structure of $\text{Area}(w_1)$.

Answer 2

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 (WayBack Machine link) 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.