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.
