这是我前一段时间在求职面试时被问到的问题。而我仍然无法找出合理的答案。
问题是：
你得到一组点（x，y）。找到2个最遥远的点。相互遥远。
例如，对于点：（0,0），（1,1），（ - 8,5） - 最远的是：（1,1）和（-8,5）因为它们之间的距离较大（0,0） - （1,1）和（0,0） - （ - 8,5）。
显而易见的方法是计算所有点之间的所有距离，并找到最大值。问题是它是O（n ^ 2），这使得它对于大型数据集而言过于昂贵。
有一种方法是在边界上有第一个跟踪点，然后计算它们的距离，前提是边界上的点数比“内部”少，但它仍然很昂贵，并且在最坏的情况下会失败。
试图搜索网络，但没有找到任何明智的答案 - 虽然这可能只是我缺乏搜索技巧。
给定一组点{（x1，y1），（x2，y2）......（xn，yn）}找到2个最远点。
我的方法：
1）。你需要一个参考点（xa，ya），它将是： xa =（x1 + x2 + ... + xn）/ n ya =（y1 + y2 + ... + yn）/ n
2）。计算从点（xa，ya）到（x1，y1），（x2，y2），...（xn，yn）的所有距离 第一个“最远点”（xb，yb）是具有最大距离的点。
3）。计算从点（xb，yb）到（x1，y1），（x2，y2），...（xn，yn）的所有距离 另一个“最远点”（xc，yc）是具有最大距离的那个。
所以你在O（n）得到了你最远的点（xb，yb）（xc，yc）
例如，对于点：（0,0），（1,1），（ - 8,5） 1）。参考点（xa，ya）=（ - 2.333,2） 2）。计算距离： 从（-2.333,2）到（0,0）：3.073 从（-2.333,2）到（1,1）：3.480 从（-2.333,2）到（-8,5）：6.411 所以第一个最遥远的地方是（-8,5） 3）。计算距离： 从（-8,5）到（0,0）：9.434 从（-8,5）到（1,1）：9.849 从（-8,5）到（-8,5）：0 所以另一个最遥远的地方是（1,1）
看直角三角形A-（x1，y1），B-（x2，y2）和距离b / w A和B是= sqrt [（| x1 | + | x2 |）^ 2 +（| y1 | + | Y2 |）^ 2]
边界点算法比比皆是（寻找凸包算法）。从那里开始，需要花费O（N）时间才能找到最远的对立点。
从作者的评论：首先在船体上找到任何一对相对的点，然后以半锁步的方式绕过它。根据边缘之间的角度，您将需要前进一个步行器或另一个步行器，但是总是需要O（N）来环绕船体。
找出所有点的平均值，测量所有点和平均值之间的差异，将该点与平均值的距离最大，并找到距离它最远的点。这些点将是凸包和两个最远点的绝对角。我最近为一个需要凸包限制在随机指向的无限平面的项目做了这个。它运作得很好。
这个问题在算法导论中介绍。它提到1）计算凸壳O（NlgN）。 2）如果在Convex Hull上有M vectex。然后我们需要O（M）才能找到最远的一对。
我发现这个有用的链接。它包括算法细节和程序的分析。 http://www.seas.gwu.edu/~simhaweb/alg/lectures/module1/module1.html
希望这会有所帮助。
找到最远对的随机算法将是
只要您预先确定“几次”，就在O（n）中，但不能保证实际找到最远的一对。但是根据你的积分，结果应该是相当不错的。 =）
您正在寻找一种算法来计算一组点的直径，Diam（S）。可以看出，这与S的凸包的直径相同，Diam（S）= Diam（CH（S））。所以首先计算集合的凸包。
现在你必须找到凸包上的所有对映点并选择具有最大距离的对。凸多边形上有O（n）对映点。因此，这给出了用于找到最远点的O（n lg n）算法。
这种技术称为旋转卡尺。这就是Marcelo Cantos在他的回答中所描述的。
如果仔细编写算法，则无需计算角度。有关详细信息，请查看此URL。
只是一些想法：
您可能只会查看定义点集凸包的点以减少数量，但它仍然看起来有点“不是最佳”。
否则，可能存在递归的四/八叉树方法，以快速绑定点集之间的一些距离并消除大部分数据。
一个起点可能是关注已经检查过的最近点问题。维基百科列出了一些选项：
如果以笛卡尔坐标给出点，这似乎很容易。很容易，我很确定我忽略了什么。随意指出我错过的东西！