如何找到两个最遥远的点？

Question

这是我前一段时间在求职面试时被问到的问题.而我仍然无法找出合理的答案.

问题是:

你得到一组点(x,y).找到2个最遥远的点.相互遥远.

例如,对于点:(0,0),(1,1),( - 8,5) - 最远的是:(1,1)和(-8,5)因为它们之间的距离较大(0,0) - (1,1)和(0,0) - ( - 8,5).

显而易见的方法是计算所有点之间的所有距离,并找到最大值.问题是它是O(n ^ 2),这使得它对于大型数据集而言过于昂贵.

有一种方法是在边界上有第一个跟踪点,然后计算它们的距离,前提是边界上的点数少于"内部",但它仍然很昂贵,并且在最坏的情况下会失败.

试图搜索网络,但没有找到任何明智的答案 - 虽然这可能只是我缺乏搜索技巧.

Answer 1

编辑:一种方法是找凸包 http://en.wikipedia.org/wiki/Convex_hull 的点的集合,然后将两个远点是这个顶点.

可能在这里回答: 找到距离彼此最远的两个点的算法

也:

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

Answer 2

边界点算法比比皆是(寻找凸包算法).从那里开始,需要花费O(N)时间才能找到最远的对立点.

从作者的评论:首先在船体上找到任何一对相对的点,然后以半锁步的方式绕过它.根据边缘之间的角度,您将需要前进一个步行器或另一个步行器,但是总是需要O(N)来环绕船体.

Answer 3

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

现在你必须找到凸包上的所有对映点并选择距离最大的对点。凸多边形上有O(n)个对映点。因此，这给出了用于查找最远点的O(n lg n)算法。

这种技术称为旋转卡尺。这就是马塞洛·坎托斯在他的回答中所描述的。

如果你仔细写算法，你可以不用计算角度。有关详细信息，请检查此URL。