Given a point set P in 2D, the problem of finding the smallest set of unit disks that cover all of P is NP-hard. We present a simple algorithm for this problem with an approximation factor of 25/6 in the Euclidean norm and 2 in the max norm, by restricting the disk centers to lie on parallel lines. The run time and space of this algorithm is O(n log n) and O(n) respectively. This algorithm extends to any Lp norm and is asymptotically faster than known alternative approximation algorithms for the same approximation factor.
翻译:从 2D 中的点设置为 P, 找到覆盖 P 全部 P 的最小的一组单盘的问题就是 NP- hard 。 我们对此问题提出了一个简单的算法, 在 Euclidean 规范中, 近似系数为 25/6, 最大值为 2, 其方法是将磁盘中心限制在平行线上。 此算法的运行时间和空间分别是 O(n log n) 和 O(n) 。 此算法扩展至任何 Lp 规范, 并且比已知的相同近似系数的替代近似算法要快。