给定半径 R，找到使圆心属于一组点 P 的面积最大化的最小圆数

Question

给定点列表 P 和半径 R，找到使面积最大化的最小点集 P。其中每个点代表一个以该点为中心的圆。

例如，给定点 (3,2)、(7,3)、(0,-1)、(5,-1)、(4,1)，点 (4,1) 是多余的，因为它不提供其他点尚未覆盖的任何额外区域。

某种回溯解决方案有效吗？我们在哪里计算每种可能组合的面积？理想情况下，有一个更有效的解决方案，因为我希望它能够处理大量点。

另一个例子：

在这种情况下，答案是所有点，因为每个点都对覆盖的总面积做出贡献。中间的部分给出了一些以黄色突出显示的区域。

是否有可以推广到任意半径的解决方案？也就是说，每个点都有自己的半径。

Answer 1

如果给定n个中心点，则最多只需要考虑n²“兴趣点”，包括：

• 给定的圆心；和
• 每对圆心最多有 2 个圆交点。

如果兴趣点不与任何圆相交（它必须是中心点），则它代表一个明显的封闭区域。找到包含它的所有圆圈。

否则，如果感兴趣的点与 k 个圆相交，则它最多与 2k 个封闭区域相邻。对于每个区域，找到包含它的所有圆圈。

以上所有操作都可以在 O(n² log n) 时间内完成。

现在你有一堆圆集，每个圆集都包含覆盖某个区域的圆集。为每个不同的圆圈集分配一个 ID。

然后，对于每个圆心，构造其圆覆盖的所有圆集的 ID 集。

你已经将你的问题转化为集合覆盖问题——你的目标是找到覆盖所有ID的最小数量的中心ID集合。

正如链接的维基百科文章中提到的，这是一个 NP 难题，您创建的实例可能非常简单。