线段交点

Question

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

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

请告诉我我理解得对吗？

- Tanu Saxena

---

磁盘是否排成一条直线？ - Abhishek Bansal

尝试计算你的方法是否具有O(n lg n)的复杂度，并发布你的解决方案。 - Max Leske

调查扫描线算法以找到线段的交点，看看它们是否可以适应于圆盘。 - n. m.

不，这些磁盘并不是直线排列的。 - Tanu Saxena

@MaxLeske 我认为我的算法的时间复杂度是O(nlgn)。我将维护一个按照x坐标排序的数组。当起始端点出现时，我会在树中插入一个圆盘。现在当另一个起始点出现时，我们检查与相邻圆的距离。这些圆盘可以在平衡二叉搜索树中维护。因此，时间复杂度为O(nlgn)。 - Tanu Saxena

你在评论中提到的算法确实可以在O(n log n)的时间复杂度内运行。它是否真的能够正常工作呢？ - n. m.

Answer 1

构建一个以圆心为基础的Voronoi图。这是一个O(n log n)的任务。

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

- n. m.

Answer 2

解决问题的另一种方法：

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

- salva

Answer 3

1. 使用圆的中心构建k-d树。
2. 对于每个圆 (p, r)，使用k-d树找到距离 p 小于 2r 的圆的集合 S。
3. 检查 S 中的任何一个圆是否与当前圆相交。

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

逻辑是我们循环遍历集合 O(N)，并且对于每个元素获取一个近似元素的子集 O(NlogN)，因此，先验地，复杂度是 O(N^2 logN)。但是我们还必须考虑两个随机圆之间距离小于 2r 且不相交的概率小于 3/4（如果它们相交，我们可以短路算法）。

这意味着 S 的平均大小在概率上受到限制，是一个小值。

- salva

---

“但我们还必须考虑到，两个随机圆之间距离小于2r且不相交的概率小于3/4”是什么意思？如果两个圆心距离小于2r，则它们将相交。 - Tanu Saxena

你有两个圆和两个半径（r 和 r2）。你对 r2 一无所知。在最坏的情况下，r2 可能为 0，那么两个圆不相交的概率就变成了3/4。因此，这是两个圆不相交的概率的上限。 - salva