algorithm - 段交点

Question

这是来自 CLRS 的一个问题。圆盘由一个圆加上它的内部组成，并由它的中心点和半径表示。如果两个磁盘有任何共同点，则它们相交。给出一个 O(n lg n) 时间的算法来确定一组 n 中的任意两个磁盘是否相交。

这不是我的家庭作业。我认为我们可以将每个圆的水平直径作为代表线段。如果两个订单是连续的，那么我们检查两个中心之间的距离长度。如果它小于或等于圆的半径之和，则它们相交。

如果我正确，请告诉我。

Answer 1

为磁盘中心构建 Voronoi 图。这是一个 O(n log n) 的工作。

现在为图表的每条边取相应的一对中心并检查它们的圆盘是否相交。

Answer 2

1. 用圆心构建一个 kd 树。
2. 对于每个圆(p, r)，使用 kd 树找到S中心比2rfrom更近的圆的集合p。
3. 检查是否有任何圆圈S接触当前圆圈。

我认为这个算法的平均成本是 O(NlogN)。

逻辑是我们在集合上循环O(N)，并且对于每个元素都得到一个靠近 的元素子集O(NlogN)，因此，先验的复杂度是O(N^2 logN)。但是我们还必须考虑两个随机圆相隔小于2r且不接触的概率小于3/4（如果它们接触，我们可以短路算法）。

这意味着 的平均大小在S概率上被限制为一个很小的值。

Answer 3

解决问题的另一种方法：

1. 使用直径为最大圆的网格划分平面。
2. 使用散列算法对 N 组中的网格单元进行分类。
3. 对于每个圆圈，计算它重叠的网格单元和相应的组。
4. 获取一个组中的所有圈子，然后...
   1. 检查最大的圆圈是否与组中的任何其他圆圈接触。
   2. 递归地将此算法应用于组中的剩余圆圈。

在 scala 中实现的相同算法：https ://github.com/salva/simplering/blob/master/touching/src/main/scala/org/vesbot/simplering/touching/Circle.scala