寻找两个距离最远的点的算法 - 有更好的O(n^2)算法吗？

Question

寻找两个距离最远的点的算法 - 有更好的O(n^2)算法吗？

15

在我的程序中，我有一组点。为了重新调整比例，我正在寻找相距最远的两个节点，并计算一个因子，以便将所有坐标乘以该因子，使得最大距离等于我定义的某个预定义值。

然而，我用来查找相距最远的两个点的算法对于大量的点是有问题的，因为它的复杂度是O(n^2)，伪代码（省略已经计算过的距离）：

 for each point in points:
     for each other point in points:
         if distance between point and other point > max
             max = distance between point and other point

有更快的方法吗？

- houbysoft

请参考John Feminella的优秀回答来解决类似问题。平均情况下，您应该能够获得O(n log n)的时间复杂度。 - Roger

可能是在大型集合中查找最远的球体的高效算法的重复问题。 - Beta

虽然它仍然是n^2的最坏情况，但很容易找到比朴素代码更糟糕的情况。因此，如果你知道你的点是“随机”分布的，那么这很好，但如果它们是有对手选择的，则不好。 - Charles

我发布了一个O(n)算法，其中包含一些误差边界，可能对你的特定的缩放问题有所帮助。 - gradbot

我认为这将跳过重复的索引和之前访问过的（但是以相反的顺序）索引对：for (int i = 0, j; i < (count - 1); i++) for (j = i + 1; j < count; j++) // 对于第一个循环，您可以使用（count-1）或计数，因为内部循环在那一点上无论如何都不会运行。 - FocusedWolf

显示剩余2条评论

7个回答

16

以下内容可能有助于更清晰地阐述平均情况下线性时间算法（用于有限集合的直径），并对比多维和平面几何问题。

1983年，梅吉多提出了一种确定性线性时间算法，用于最小包围圆（或高维球体）。

在一般位置上，包围圆将在其边界上具有两个或三个点，因此一旦知道边界圆，就可以“平均”在常数时间内找到最远的两个点。在更高的维度中，处于一般位置的点的数量需要增加到边界球体上（D + 1个点用于D维），实际上计算单个点对之间距离的成本随着维度的增加而线性增加。

边界圆或球体上的点子集也可以在线性时间内找到。在理论最坏情况下，所有点都位于边界圆或球体上，但这至少比所有点都位于凸包上要严格。如果球面上的点是独立扰动的，例如沿径向线，则可以确保处于一般位置，并且可以从修订后的包围球体上的仅D + 1个点中找到近似直径。这种随机逼近在维度上具有二次依赖性，但在点数上只具有线性复杂度。

如果位于边界圆上的点“排序”（当然是循环排序），则可以利用圆的“单峰性”（即到固定点的距离单调上升，直到反极点，然后下降）在线性时间内找到相距最远的一对，以分摊计算距离的成本。不幸的是，这种排序将引入O(n log n)时间复杂度的步骤，在平面情况下，这被证明是精确确定性方法的最坏情况。

2001年，拉莫斯成功地展示了三维集合的O(n log n)确定性算法，但该技术非常复杂，实现可能比枚举所有对的搜索不切实际或更慢，直到大型数据集。

对于更高维度，许多作者考虑了随机化或近似算法。见Piotr Indyk's thesis (2000) 中各种接近问题的依赖于多项式的近似方法。

- hardmath

13

正如这个答案中提到的，您正在寻找N个点的集合的"直径"，这是计算几何中众所周知的问题。基本上有两个步骤：

找到这些点的凸包。存在算法是O(N ln N)的，最坏情况下。在实践中，QuickHull通常是一个快速的选择，尽管可能是O(N^2)的最坏情况。QHull实现方便从命令行调用。CGAL库提供了C ++实现
凸包上的反极对是最远点的候选。可以使用像旋转卡尺这样的算法在O(N)时间内搜索反极点。

问题可以概括为 “所有最远对” 问题：对于每个点 i，找到最远的点 j ——我们现在正在寻找 N 对点。解决方案再次使用凸包，但现在第二部分可以使用矩阵搜索算法完成。

- Kipton Barros

4

其实不是 - 一种常见的方法是将点分组成簇，然后存储簇之间的距离。

这样，如果你已经确定澳大利亚距离更远，就无需检查纽约的某个房子是否距离巴黎最远。

- Martin Beckett

3

从 A 到 B 的距离与从 B 到 A 的距离相同。通过这种方法，您可以轻松修改算法以消除一半的计算。它仍将是 O(n^2)，但速度会快两倍。

也就是说，不是计算距离矩阵 P x P 的所有非对角线元素：

P = {A, B, C, D, ...}

  + A + B + C + D + ...
A |   | * | * | * | ...
B | * |   | * | * | ...
C | * | * |   | * | ...
D | * | * | * |   | ...
  |   |   |   |   |

您可以计算上三角形：

  + A + B + C + D + ...
A |   | * | * | * | ...
B |   |   | * | * | ...
C |   |   |   | * | ...
D |   |   |   |   | ...
  |   |   |   |   |

或者是下三角形：

  + A + B + C + D + ...
A |   |   |   |   | ...
B | * |   |   |   | ...
C | * | * |   |   | ...
D | * | * | * |   | ...
  |   |   |   |   |

- Matt Ball

我其实已经在做那个了，只是为了简单起见，我没有把它放在伪代码里。 - houbysoft

2

如果你经常执行这个查询，但是点的变化不大，你可以进行预计算来加快速度。

每个点都可以存储它最远的点，并在每次添加新点时重新检查是否更远。

当你查询时，只需遍历所有点并查看它们的缓存点。

最终你会得到 O(n) 的新点输入和 O(n) 的最远查询。

- Variant

1

我不确定将点放入空间索引并查询是否会导致O(n log n)算法。

- Peter G.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gradbot · Accepted Answer

如果你只需要比例而不是精确的点，你可以在O(n)的时间内完成，并具有一定的误差范围。考虑制作一个边界框的简单情况。计算所有点的最小x值、最大x值、最小y值和最大y值。这四个数字给出了一个最大的边界框，最大误差约为30％的1-(1/sqrt(2))。您可以通过向正方形添加更多的边来减少这个误差。考虑八边形的情况。要计算其他边的最小和最大值，您必须旋转坐标系。

错误与运行时间的关系如下所示。

形状 - 运行时间 - 最大误差

- 正方形 - 2N - 30% - 八边形 - 4N - 16% - 16边形 - 8N - 4% - 32边形 - 16N - 1%

这是我想到的最大误差方程式。

angle = 180 / sides
max_error = (1 / cos angle) - cos angle

如果需要我添加一张说明此事的图表，请告诉我。