给定圆心，找到最小半径的一组圆来完全覆盖另一个集合。

Question

我有一个几何问题需要解决： 给定圆心在原点C(0, 0)，半径为1的圆。圆内给出N个点，这些点代表N个不同圆的圆心。你需要找到最小的小圆半径（所有圆的半径相等），以覆盖大圆的所有边界。

圆的数量是：3≤N≤10000，问题必须以P位小数的精度解决，其中1≤P≤6。

例如：
N = 3且P = 4

坐标为：
(0.193, 0.722)
(-0.158, -0.438)
(-0.068, 0.00)

小圆的半径为：1.0686。

我的想法是使用二分查找来找到半径，并尝试找到小圆和大圆之间的所有交点。每个交点将产生一条弧线。下一步是将弧线的坐标“投影”到X轴和Y轴上，结果是一些区间。如果X轴和Y轴的区间重合在[-1,1]区间内，则意味着所有圆都被覆盖了。

为避免精度问题，我考虑在0和2×10^P之间进行搜索，并将半径取为10^P，从而消除逗号后的数字。但我的问题是如何模拟圆的交点，以及之后如何查看结果区间的重合是否形成[-1,1]区间。

欢迎提出任何建议！

- ZLMN

---

你的算法只考虑了圆的周长，但是有可能整个周长被覆盖了，而中间却存在未覆盖的区域。 - interjay

我认为你的示例解决方案可能是不正确的。 "大圆"的半径为1，因此使“小圆”的半径也为1将满足您示例中的问题。 1可能不是最小值，但肯定比1.0686更好。 - Don Roby

这是个棘手的问题；我很感兴趣看到一个不涉及检查每个可能点的覆盖答案。 - jamesbtate

在OP翻译和复制此内容的文档中，它说要覆盖圆圈，而不是它的面积。我还应该说，这来自于正在进行的罗马尼亚计算机科学竞赛，将在大约30小时后结束，对于可能涉及此事的人。 - IVlad

@IVlad - 是的，你说得对，这个问题来自一个正在进行的比赛（f11竞赛），但正如你所看到的，我并没有要求解决方案，我只是提出了我的解决方案，并请求一些在解决“交叉”部分方面的指导。@interjay，@belisarius。IVlad是正确的。正如您从原始翻译中所看到的，该问题要求覆盖边界（我在发布问题后才发现）。 - ZLMN

Answer 1

你的集合中的每个点都必须覆盖其在点集 Voronoi 图中的单元格与以原点为圆心的测试圆的交集。为了找到半径，首先计算出你的点集的 Voronoi 图。现在通过将所有无限边与目标圆相交来“闭合”该 Voronoi 图。然后对于集合中的每个点，检查到其“闭合” Voronoi 单元格中所有点的距离。最大值应该是你的解决方案。直到你的解决方案半径大于1（因为那时“小”圆弧会更弯），这些单元格被圆弧而不是直线关闭也没有关系。在这种情况下，你还必须检查距离该圆弧最远的单元格中心的点。

- ltjax

Answer 2

我可能漏掉了什么，但似乎你只需要找到圆上一点与给定点之间的最大最小距离。

也就是说，如果你考虑圆上所有的点，并且取每个点到给定点的最小距离，然后取所有这些最小值的最大值 - 你就找到了半径。

当然，这不是一个算法，因为有无限多个点。

我想我会做以下操作：

1. 找到周长和点集之间的最小距离，这是你的初始半径R。
2. 检查整个圆是否被覆盖，如下所示： 对于任意两个距离超过2R的点，请检查是否覆盖了整个线段（对于每个点，请检查其周围的圆是否相交，如果是，则删除该线段并继续）。这应该需要o(N^3)的时间（你要为每对点迭代所有点）。如果我没错的话（尽管我没有正式证明），当且仅当所有线段都被覆盖时，圆被覆盖。
3. 从未被覆盖的线段中选择最长的一条，并将其长度的一半加到R上。
4. 重复。

这个算法本身不会完全覆盖圆形，但很容易证明它呈指数收敛到完全覆盖，因此它应该能够在合理的迭代次数内以任意精度找到所需的半径。

希望这有所帮助。

- Shai Deshe

---

嗯，我刚想到了一个反例，抱歉。 - Shai Deshe