如何找到两个最远的点？ [英] How to find two most distant points?

问题描述

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

问题是：

正在给定的点（X，Y）的。找到2最远点。彼此远离。

例如，对于点：（0,0），（1,1），（-8，5） - 最远处是：（1,1）和（-8,5），因为它们之间的距离是从两个（0,0）放大 - （1,1）和（0,0） - （ - 8,5）。

显而易见的方法是计算所有点之间的所有距离，并找到最大。的问题是，它是O（n ^ 2），这使得对大型数据集它昂贵。

有一个与第一个跟踪点是在边界上，然后方法计算距离对他们来说，在premise会有那么点边界不是内部，但它仍然是昂贵的，并且将失败在最坏的情况下

试过在网上搜索，但没有发现任何合理的答案 - 尽管这可能是简单的我缺乏的搜索技巧

解决方案

  

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

可能回答这里： <一href="http://stackoverflow.com/questions/477591/algorithm-to-find-two-points-furthest-away-from-each-other">http://stackoverflow.com/questions/477591/algorithm-to-find-two-points-furthest-away-from-each-other

另外：

• <一个href="http://mukeshiiitm.word$p$pss.com/2008/05/27/find-the-farthest-pair-of-points/">http://mukeshiiitm.word$p$pss.com/2008/05/27/find-the-farthest-pair-of-points/

This is a question that I was asked on a job interview some time ago. And I still can't figure out sensible answer.

Question is:

you are given set of points (x,y). Find 2 most distant points. Distant from each other.

For example, for points: (0,0), (1,1), (-8, 5) - the most distant are: (1,1) and (-8,5) because the distance between them is larger from both (0,0)-(1,1) and (0,0)-(-8,5).

The obvious approach is to calculate all distances between all points, and find maximum. The problem is that it is O(n^2), which makes it prohibitively expensive for large datasets.

There is approach with first tracking points that are on the boundary, and then calculating distances for them, on the premise that there will be less points on boundary than "inside", but it's still expensive, and will fail in worst case scenario.

Tried to search the web, but didn't find any sensible answer - although this might be simply my lack of search skills.

解决方案

EDIT: One way is to find the convex hull http://en.wikipedia.org/wiki/Convex_hull of the set of points and then the two distant points are vertices of this.

Possibly answered here: http://stackoverflow.com/questions/477591/algorithm-to-find-two-points-furthest-away-from-each-other

Also:

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

这篇关于如何找到两个最远的点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！