如何find两个最远的点？
这是我前段时间在面试时被问到的一个问题。 而我仍然无法弄清楚明智的答案。
问题是：
你有一组点（x，y）。 find2个最远的点。 彼此遥远。
例如，对于点（0,0），（1,1），（-8,5） – 最远的是：（1,1）和（-8,5），因为它们之间的距离大于（0,0） – （1,1）和（0,0） – （ – 8,5）。
显而易见的方法是计算所有点之间的所有距离，并find最大值。 问题在于它是O（n ^ 2），这对于大型数据集来说过于昂贵。
对边界上的第一个跟踪点有一个方法，然后计算它们的距离，前提是边界上的点比“内部”要less，但是它仍然很昂贵，在最坏的情况下会失败。
试图searchnetworking，但没有find明智的答案 – 虽然这可能只是我缺乏search技能。
编辑：一种方法是find一组点的凸包http://en.wikipedia.org/wiki/Convex_hull ，然后两个远点是这个的顶点。
在这里可能回答： algorithmfind距离彼此最远的两个点
也：
边界点algorithm比比皆是（查找凸包algorithm）。 从那里，应该花费O（N）时间来find最远的相对点。
从作者的评论：首先find船体上任何一对相反的点，然后以半锁步行走。 根据边缘之间的angular度，你将不得不推进一个步行者或另一个，但总是需要O（N）环绕船体。
这个问题在algorithm介绍中介绍。 它提到1）计算凸包O（NlgN）。 2）如果在凸包上有M vectex。 那么我们需要O（M）find最远的一对。
我发现这个有用的链接。 它包括algorithm细节和程序的分析。 http://www.seas.gwu.edu/~simhaweb/alg/lectures/module1/module1.html
希望这将是有益的。
您正在寻找一种algorithm来计算一组点的直径Diam（S） 。 可以certificate，这与S的凸包的直径Diam（S）= Diam（CH（S））相同 。 所以首先计算集合的凸包。
现在你必须find所有的凸包上的反对点，并select最大距离的一对。 在凸多边形上有O（n）个对angular点。 所以这给出了一个O（n lg n）algorithm来find最远的点。
这种技术被称为旋转卡尺 。 这是马塞洛坎托斯在他的回答中所描述的。
如果你仔细地写出algorithm，你可以不用计算angular度。 有关详细信息，请检查此URL 。
一个随机algorithmfind最遥远的一对将是
- select一个随机点
- 得到最遥远的点
- 重复几次
- 删除所有访问点
- select另一个随机点并重复几次。
只要你预定了“几次”，你就在O（n）中，但不能保证实际find最远的一对。 但取决于你的分数的结果应该是相当不错的。 =）
只是几个想法：
你可能只看点定义你的点集凸包，以减less数量，…但它仍然看起来有点“不理想”。
否则，可能会有一个recursion四/八叉树方法来快速限制点集之间的一些距离，并消除大部分数据。
一个起点可能是看最近的问题，这已经过检查。 维基百科列出了一些选项：
如果以笛卡尔坐标给出点，这似乎很容易。 很容易，我敢肯定，我忽略了一些东西。 随意指出我错过了什么！
- 找出x，y和z坐标（总共6点）的最大值和最小值的点。 这些应该是所有边界点中最“偏远的”。
- 计算所有的距离（30个独特的距离）
- find最大距离
- 对应于这个最大距离的两点是你正在寻找的。
find所有点的平均值，测量所有点和平均值之间的差值，取距离平均值的最大距离，find离它最远的点。 这些点将是凸包和两个最远点的绝对angular落。 我最近做了这个项目，需要凸壳限制在随机指挥无限飞机。 它运作良好。
给定一组点{（x1，y1），（x2，y2）…（xn，yn）}find2个最远的点。
我的方法是：
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）
（x1，y1），B-（x2，y2），距离b / w A和B是= sqrt | Y2 |）^ 2]
