假设我们有一组点$p_1,\ldots,p_n\in\mathbb R^d$以及一组权重$w_1,\ldots,w_n\in\mathbb R$. 回想一下，与该对关联的电池$(p_k,w_k)$是（谁）给的：

$$\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$$ 作为一种特殊情况，当所有权重都为零时$\mathcal C_k$

假设所有，是否存在一种易于实现、中等效率（至少对于低维）的数值算法来查找一组点对于所有使用？$\mathcal C_k\neq\emptyset$$k$$d$$x_1,\ldots,x_n\in\mathbb R^d$$x_k\in\mathcal C_k$$k\in\{1,\ldots,n\}$

我不在乎我们找到哪一点，只要它在电池内部即可。显而易见的算法“构建功率图”很难实现——尤其是对于 ——并且可能是浪费的。我的希望是，对于低可能有一种更简单的方法来解决这个问题，它的规模大致在。$d>3$$d$$n$

如果有帮助，我们可以假设我们有一组点使得每个离不太远，即尝试进行本地更新。$\tilde x_1,\ldots,\tilde x_n\in\mathbb R^d$$x_k$$\mathcal C_k$