寻找点之间的最小距离的最快方法

Question

我有一组二维点，需要找到其中距离最短的点对，希望您能帮我翻译下如何最快地解决这个问题。

最优解是什么？我的方法是使用快速排序将它们排序，然后计算距离。这样的时间复杂度为O(nlogn + n) = O(nlogn)。

是否可能在线性时间内完成？

谢谢。

- Pietr

---

你如何使用快速排序算法对二维数据进行排序？这有助于找到最接近的两个点吗？ - Daniel Brückner

我只是按x坐标对它们进行排序。基本上，看起来我实现了http://en.wikipedia.org/wiki/Closest_pair_problem中解释的算法。首先按x排序，然后分而治之。所以看起来没有更快的方法。 - Pietr

按X排序实际上没有什么价值，因为最接近的点可能没有接近的X值。而按X排序并不能减少需要将每个点与每个其他点进行比较以找到最接近的一对的需求。 - S.Lott

实际上是这样的。请查看上面的维基百科链接和分治解决方案。它的时间复杂度为O(N log N)。 - Pietr

维基百科文章称，如果 floor 是一个常数时间操作，那么实际上是 O(n log log n)（然而，我认为对于任意大的数字，它实际上并不是）。 - Matthew Flaschen

看起来你假设快速排序的时间复杂度是O(n*log2(n))，但是快速排序的最坏情况是O(n^2)。 - Nixuz

Answer 1

实际上：

最近点对问题或最近对问题是计算几何学中的问题：在度量空间中给定n个点，找到一对距离最小的点...

在假设floor函数可以在常数时间内计算的计算模型中，该问题可以在O(n log log n)时间内解决。如果允许随机化与floor函数一起使用，则该问题可以在O(n)时间内解决。

- leiz

Answer 2

如果您可以从每个点探测出一个恒定数量并使用迭代加深深度优先搜索，则您永远不会检查比两个最接近的点更远的距离...并且由于您不依赖于失败的传递，因此您永远不需要重新计算ID DFS所倾向的方式。

- max

Answer 3

不行。在O(n ^ 2)中，所有点之间的最小距离都必须进行比较，因为您必须将每个点与其他每个点进行比较。从技术上讲，它是n * n / 2，因为您只需要填充矩阵的一半。

有更快的算法可以找到给定点的最近邻居。不幸的是，您必须对每个点执行此操作，以找到最接近的两个点。

- S.Lott

---

该图并不是一个算法。Fortune算法生成了这个图。http://en.wikipedia.org/wiki/Fortune%27s_algorithm。我不确定它是否适用，因为它分割空间而不是比较点。 - S.Lott