Hitting or avoiding balls in Euclidean space
Hitting or avoiding balls in Euclidean space
复制标题
在欧几里得空间中击球或躲避球
DOI：
10.1023/a:1018901600127
复制
发表时间：
1997
影响因子：
4.8
通讯作者：
T. Ibaraki
中科院分区：
文献类型：
--
作者：
Y. Crama;T. Ibaraki
我们研究了以下几类几何问题的算法复杂性：给定欧氏空间中的一个“可行”盒子和一组球，找到一个分别被尽可能少或尽可能多的球所覆盖的可行点。我们证明，所有这些问题在其最一般的版本中都是NP-困难的。我们得到了它们的一维形式的复杂性的严格下界和上界。最后，我们证明了当空间的维度固定时，所有这些问题都可以在多项式时间内得到解决。
We investigate the algorithmic complexity of several geometric problems of the following type: given a "feasible" box and a collection of balls in Euclidean space, find a feasible point which is covered by as few or, respectively, by as many balls as possible. We establish that all these problems are NP-hard in their most general version. We derive tight lower and upper bounds on the complexity of their one-dimensional versions. Finally, we show that all these problems can be solved in polynomial time when the dimension of the space is fixed.