# Finding points inside cells of power (generalized Voronoi) diagram

Suppose we have a set of points $$p_1,\ldots,p_n\in\mathbb R^d$$ as well as a set of weights $$w_1,\ldots,w_n\in\mathbb R$$. Recall that the power cell associated to the pair $$(p_k,w_k)$$ is given by: $$\mathcal C_k:=\{x\in\mathbb R^d:\|x-p_k\|_2^2-w_k\leq\|x-p_\ell\|_2^2-w_\ell\ \forall \ell\in\{1,\ldots,n\}\}\subseteq\mathbb R^d$$ As a special case, the $$\mathcal C_k$$'s become Voronoi cells when all the weights equal zero.

Assuming $$\mathcal C_k\neq\emptyset$$ for all $$k$$, is there an easily-implemented, moderately efficient (at least for low dimensions $$d$$) numerical algorithm for finding a set of points $$x_1,\ldots,x_n\in\mathbb R^d$$ with $$x_k\in\mathcal C_k$$ for all $$k\in\{1,\ldots,n\}$$?

I don't care which point we find, so long as it is inside the power cell. The obvious algorithm "construct the power diagram" is hard to implement---especially for $$d>3$$---and potentially wasteful. My hope is that for low $$d$$ maybe there's a simpler way to solve this problem that scales roughly in $$n$$.

If it helps, we can possibly assume we have a set of points $$\tilde x_1,\ldots,\tilde x_n\in\mathbb R^d$$ such that each $$x_k$$ isn't too far away from $$\mathcal C_k$$, i.e., try to make a local update.

• How does the power cell typically look like? Is it a polyhedron? – Wolfgang Bangerth May 15 '20 at 15:57
• yes, it's still an intersection of half planes – Justin Solomon May 15 '20 at 20:07
• You might get more responses if you added a picture of the power cells for a few different values of the $w_\ell$ for a given (small) set of points $p_k$. – Wolfgang Bangerth May 15 '20 at 21:37
• If you can describe a power cell as a (potentially infinite) polyhedron, then there are sampling algorithms that give you points within it. – Wolfgang Bangerth May 15 '20 at 21:38
• Do the weights $w_i$ vary a lot, or do they have similar values ? (depending on that, I may have a solution...) – BrunoLevy May 17 '20 at 18:42