algorithm - 找到所有给定圆圈覆盖的点

Question

给定 n (n <= 1000) 个圆 ((x;y), r) 其中 (x;y) = 圆心坐标，r = 半径。x, y, r <= 10^6。x, y, r, 可以是实数。

问题是找到所有圆圈覆盖的点（x;y），或者确定没有这样的点。点坐标也可以是实数。

不知道怎么做，有人可以帮忙吗？

标签： algorithmgeometry

Answer 1

假设你所说的圆圈是数学家所说的封闭圆盘，那么就有一个具有简单数据结构的 O(n²) 时间算法。

对于从 1 到 n 的 k，算法在前 k 个磁盘的交点中找到一个点，假设存在这样的点。从第一个磁盘的中心开始。对于第一个之后的每个磁盘，检查当前点是否属于该磁盘。如果是这样，那就太好了。如果不是，则交点为空，或者交点包含当前圆盘边界上的一个点（从当前点到所有圆盘交点中任意点的线段必须穿过边界）。在这种情况下，通过将边界（一个圆）与之前的每个圆盘相交来找到一个新点，这是一个更简单的一维问题。

如果我们随机化磁盘的顺序，这可能会更快，但我还没有得出一个证明。当 n ≤ 1000 时，希望 O(n²) 足够快。

Sharir ("Intersection and Closest-Pair Problems for a Set of Planar Discs", 1985) 可能给出了 O(n log² n) 时间算法，但我无法从摘要中看出。