相关疑难解决方法(0)

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

问题是:

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

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

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

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

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

在我的计划中,我有一套积分.出于重新缩放的目的,我正在搜索最远的两个节点,然后计算乘以所有坐标的因子,使得最大距离等于我定义的某个预定义的距离.

然而,我用来找到最远的两个点的算法对于大的点集是有问题的,因为它是O(n^2); 伪代码(已经计算的距离被跳过):

 for each point in points:
     for each other point in points:
         if distance between point and other point > max
             max = distance between point and other point

有更快的东西吗？