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.

  • $\begingroup$ How does the power cell typically look like? Is it a polyhedron? $\endgroup$ – Wolfgang Bangerth May 15 '20 at 15:57
  • $\begingroup$ yes, it's still an intersection of half planes $\endgroup$ – Justin Solomon May 15 '20 at 20:07
  • $\begingroup$ 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$. $\endgroup$ – Wolfgang Bangerth May 15 '20 at 21:37
  • $\begingroup$ If you can describe a power cell as a (potentially infinite) polyhedron, then there are sampling algorithms that give you points within it. $\endgroup$ – Wolfgang Bangerth May 15 '20 at 21:38
  • $\begingroup$ Do the weights $w_i$ vary a lot, or do they have similar values ? (depending on that, I may have a solution...) $\endgroup$ – BrunoLevy May 17 '20 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.