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

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 图。现在通过将所有无限边与目标圆相交来“关闭”此泰森图。然后，对于集合中的每个点，检查到其“闭合”voronoi 单元的所有点的距离。最大值应该是你的解决方案。

在您的解决方案半径大于 1 之前，单元格通过圆弧而不是直线通过测试圆闭合应该没有关系（因为这样“小”圆的弧度会更强）。在这种情况下，您还必须检查从单元中心到该弧的最远点。