如何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四/八叉树方法来快速限制点集之间的一些距离,并消除大部分数据。

一个起点可能是看最近的问题,这已经过检查。 维基百科列出了一些选项:

http://en.wikipedia.org/wiki/Closest_point_query

如果以笛卡尔坐标给出点,这似乎很容易。 很容易,我敢肯定,我忽略了一些东西。 随意指出我错过了什么!

  1. 找出x,y和z坐标(总共6点)的最大值和最小值的点。 这些应该是所有边界点中最“偏远的”。
  2. 计算所有的距离(30个独特的距离)
  3. find最大距离
  4. 对应于这个最大距离的两点是你正在寻找的。

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]