N个圆的共同重叠

Question

我想用半径和中心坐标表示N个圆，我想知道是否存在一种算法来确定点P是否存在，使得P在所有圆内。

Answer 1

一种简单的 O(n^3) 方法是简单地计算每对圆的交点，然后对每个交点进行测试以查看它是否在所有圆中。

将有 O(n^2) 个交点，测试每个交点都需要 O(n)，因此总体来说是 O(n^3)。

我相信所有圆内都有点而不是交点的唯一方法是最里面的圆完全位于其他圆内，所以您还应该测试每个圆的中心。