c - 给定中心，找到一组圆的最小半径，使它们完全覆盖另一个

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]。

欢迎任何建议!

Answer 1

集合中的每个点都必须覆盖其在点集的 voronoi 图中的单元与原点周围的测试圆的交点。

要找到半径，首先计算 voronoi diagram你的点集。现在通过将所有无限边与目标圆相交来“关闭”此 voronoi 图。然后对于集合中的每个点，检查到其“封闭”voronoi 单元的所有点的距离。最大值应该是您的解决方案。

在您的解决方案半径大于 1 之前，单元格被测试圆弧而不是直线封闭应该无关紧要(因为“小”圆弧会更强)。在这种情况下，您还必须检查从像元中心到该弧线的最远点。