如何找到两个最远的点？

Question

这是我以前在一次工作面试中被问到的问题，但我仍然无法想出一个明智的答案。

问题是：

给你一组点(x,y)，找出其中距离最远的两个点。它们之间的距离要求最大。

例如，对于这些点：(0,0), (1,1), (-8,5) - 距离最远的是：(1,1) 和 (-8,5)，因为它们之间的距离比 (0,0)-(1,1) 和 (0,0)-(-8,5) 都要大。

显而易见的解决方法是计算所有点之间的距离并找到最大值。但是这种方法的时间复杂度是O(n^2)，对于大型数据集来说代价太高了。

还有一种方法是首先跟踪位于边界上的点，然后计算它们之间的距离，这基于边界上的点数量应该比“内部”少的前提下，但是这种方法仍然很耗时，并且在最坏情况下可能会失败。

我尝试过搜索网络，但没有找到任何合理的答案 - 尽管这可能只是我的搜索技巧不足所致。

- user80168

---

如果您可以在O(nlogn)的时间复杂度内进行排序，请尝试使用它。 - Gabriel Ščerbák

你不能“排序”一个多维空间，更准确地说，你可以用许多不同的方式对其进行排序。 - fortran

你知道可能没有唯一的答案，你需要最远的所有对还是只需要一个最远的一对？ - jk.

@jk - 只需最遠的一對。 - user80168

Answer 1

针对这个具体问题，仅有欧几里得点列表，一种方法是找到该点集的凸包。然后可以使用旋转卡尺法遍历凸包一次来找到这两个最远的点。

以下是O(N log N)实现方法：

• http://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/

如果点的列表已经排好序，可以去掉排序部分以获得最优O(N)复杂度。

---

针对更一般的在图中查找最远点的问题： Algorithm to find two points furthest away from each other 被接受的答案的时间复杂度为O(N^2)。

- zaf

---

这个问题是关于图算法，而不是计算几何，对吗？ - P Shved

你可以将问题建模为一个完全带权图。 - jk.

Answer 2

边界点算法很多（查找凸包算法）。从那里开始，需要 O(N) 时间来找到最远的相对点。

作者评论中提到：首先在外壳上找到任何一对相对点，然后半锁步地绕着它走。根据边缘之间的角度，您将不得不推进一个行者或另一个行者，但穿越外壳始终需要 O(N) 的时间。

- Marcelo Cantos

---

现在假设所有给定的N个点都在凸包上。仍然是O(N)吗？ - P Shved

抱歉，那比我现在想做的工作还要多。 - Marcelo Cantos

好吧，您的评论无论如何都是此页面上正确算法的最佳解释，因此我将其放入答案文本并点赞。 - P Shved

谢谢Pavel！顺便说一下，我并不是想要轻视你（我的最后一条评论比我想象中的更糟糕）。这只是需要一些琐碎的几何和边缘情况才能做到正确。 - Marcelo Cantos

@Marcelo，哦，在计算几何中说“完整算法”通常意味着“在变得无聊之前尽可能完整” :-) - P Shved

Answer 3

你正在寻找计算一组点的直径的算法，Diam(S)。可以证明这与S的凸包的直径相同，Diam(S) = Diam(CH(S))。因此，首先要计算集合的凸包。

现在，您需要找到凸包上的所有对踵点，并选择距离最远的一对。凸多边形上有O(n)个对踵点。因此，这提供了一个O(n lg n)的算法来查找最远的点。

这种技术称为旋转卡尺。这就是Marcelo Cantos在他的答案中描述的内容。

如果你仔细编写算法，可以不用计算角度。详情请查看此URL。

- mrk

---

URL链接已经失效了.. 你有没有可能提供一个新的链接？ - sgerbhctim

@sgerbhctim，您可以在此处找到它：https://web.archive.org/web/20180528104521/http://www.tcs.fudan.edu.cn/~rudolf/Courses/Algorithms/Alg_ss_07w/Webprojects/Qinbo_diameter/2d_alg.htm - Alberto Schiabel

Answer 4

这个问题被介绍在《算法导论》中。其中提到了1）计算凸包O(NlgN)。2）如果凸包上有M个顶点，则需要O(M)来找到最远的一对。

我找到了这些有用的链接。它包括算法细节和程序分析。 http://www.seas.gwu.edu/~simhaweb/alg/lectures/module1/module1.html 希望这会有所帮助。

- yuan

---

通过wayback机器修复链接 [URL] (https://web.archive.org/web/20170620040641/http://www2.seas.gwu.edu/~simhaweb/alg/lectures/module1/module1.html) - DaemonFire

Answer 5

一种用于查找最远点对的随机算法为：

• 选择一个随机点
• 获取距离该点最远的点
• 重复几次
• 移除所有已访问的点
• 选择另一个随机点并重复几次。

只要您预先确定“几次”，就可以在O(n)时间内完成，但不能保证实际上找到最远的点对。但根据您的点集，结果应该相当不错。 =)

- Jens

---

考虑一下，然后更正或删除您的答案，以免被踩：想象一下，您有一个几乎是正方形的点集，{A =（0,0），B =（10,10），C =（10,0），D =（0,11）}; 最远的点是BD（距离= 14.86）; 但是，如果您尝试从A或B开始，您会感到想要删除C（AC = BC = 10）或D（AD = 11，BD = 10.05），因为它们比相反的顶点（AC = 14.14）更接近所选的顶点，而实际上最长的距离确实是14.86。 - ANeves

在你的例子中，CD是最远的点，而不是BD。从A或B开始，步骤2中总是选择另一个点，因此只有这两个点在步骤4中被删除。 - Jens

Answer 6

找到所有点的平均值，测量所有点与平均值之间的差异，选取距离平均值最远的点并找出距离它最远的点。这些点将是凸包的绝对角和两个最远的点。最近我在一个需要凸包限制在随机定向无限平面上的项目中做了这个，效果很好。

请注意评论：该解决方案不能保证产生正确答案。

- Rich Colburn

---

我认为这个答案对像我一样不是数学天才的人来说最易懂。谢谢。 - tjebo

假设这是正确的，这是对这个问题最好的答案（在我看来），因为它是O(n)，可以推广到三维，并且实现起来很简单。 - Garrett Gutierrez

这个算法不起作用。请尝试使用这些点：(-10, 0)，(100, 0)，(0, 70)，(0, -70)。离平均值最远的点是(100, 0)，但两个最远的点是(0, 70)和(0, -70)。 - lvella

任何使用“平均”位置（即重心）的算法都可能受到点在“不良”位置附近不均匀聚集的影响，因此我认为这样的算法不太可能有效地找到正确的结果。但我想在许多情况下它可以找到一个很好的近似值。如果您可以接受快速的近似解决方案，那么“平均”算法对于均匀分布的点可能可以正常工作，而选择边界框上的点的方法对于不均匀分布的点可能可以正常工作（具有sqrt2）。 - Adam Gawne-Cain

这仅适用于一维情况。甚至不适用于二维情况：想象一个宽度为4，高度为3且在交叉点处具有平均值的T形图案。底部点距离平均值最远，仅与左右点距离为sqrt(2²+3²)=3.6，而不是4。 - comonad

Answer 7

几点想法：

你可以只关注定义点集凸包的点以减少数量，但这仍然看起来有点“不够优化”。

否则，可能存在一种递归四叉树或八叉树方法，可以快速限定点集之间的一些距离并消除数据的大部分。

- Adrien

Answer 8

如果给出笛卡尔坐标系中的点，这似乎很容易。如此容易，以至于我相当确定自己漏掉了某些东西。请随意指出我漏掉的部分！

1. 找到具有最大和最小值的 x、y 和 z 坐标的点（总共 6 个点）。这些应该是所有边界点中最“遥远”的点。
2. 计算所有距离（30 个唯一距离）
3. 找到最大距离
4. 对应于此最大距离的两个点就是您要寻找的点。

- Justin Henrie

---

好的，经过进一步思考，这并不能保证找到最远的两个点。唉！但是，它确实可以给出由点数组勾画的区域的最小尺寸，该尺寸不会超过sqrt(2)的比例。可能会有用！ - Justin Henrie

Answer 9

一个运行时间复杂度为O(N)的解决方案是上面答案的组合。详细来说： （1）如果你使用计数排序作为内部极角排序并愿意使用舍入到最近整数[0, 359]（包括边界）的角度，那么可以在运行时间复杂度为O(N)的情况下计算出凸包。 （2）请注意，此时凸包上的点数为N_H，通常小于N。 我们可以根据Cormen等人的《算法导论》第33-5练习中的信息推测出凸壳的大小。对于单位半径圆盘、具有k个边的凸多边形和2-D正态分布的稀疏凸壳分别为n^(1/3)，log_2(n)，sqrt(log_2(n))。

然后，最远点对问题在凸壳上的点之间进行比较。这是N_H^2，但是每个领先点的距离点的搜索可以在距离开始减少时截断，如果按照凸包的顺序遍历点（这些点从第一个点开始按逆时针顺序排序）。因此，这一部分的运行时间复杂度为O(N_H^2)。

由于N_H^2通常小于N，所以最远点对的总运行时间复杂度为O(N)，但有一个注意事项，即使用整数度数角来将凸包中的排序降至线性。

- nichole

Answer 10

这里有一个好的解决方案，可以在O(n log n)的时间复杂度内完成。它被称为旋转卡壳算法。 https://www.geeksforgeeks.org/maximum-distance-between-two-points-in-coordinate-plane-using-rotating-calipers-method/

首先，您需要找到凸包，使用Graham扫描算法可以在O(n log n)的时间复杂度内完成。只有凸包的点才能提供给您最大的距离。该算法会按照顺时针遍历凸包中的所有点。稍后会用到这个性质。

其次，对于凸包上的所有点，您需要找到该凸包上最远的点（这里称为反极点）。您不必单独找到所有反极点（这将花费二次时间）。假设凸包的点称为p_1，...，p_n，并且它们的顺序对应于顺时针遍历。凸多边形有一个特性，当您按顺时针顺序迭代凸壳上的点p_j并计算距离d（p_i，p_j）时，这些距离首先不会减少（也许增加），然后不会增加（也许减少）。因此，在这种情况下，您可以轻松找到最大距离。但是，当您找到p_i的正确反极点p_j *时，您可以从该p_j *开始搜索p_{i + 1}的候选点。您无需检查所有先前看到的点。总共，p_i通过点p_1，...，p_n一次迭代，并且p_j最多迭代这些点两次，因为p_j永远无法赶上p_i，因为这将给出零距离，并且我们停止当距离开始减少时。

- Michał Słodki