计算列表中两点最大距离的最有效方法是什么？

Question

我有一个L点列表(x, y)和通常的欧几里德距离测量

如何找到此列表中两点的最大距离？或者,更正式地说:我如何找到

琐碎的方法

解决这个问题的最简单方法似乎是尝试一切:

def find_max_dist(L):
    max_dist = d(L[0], L[1])
    for i in range(0, len(L)-1):
        for j in range(i+1, len(L):
            max_dist = max(d(L[i], L[j]), max_dist)
    return max_dist

为了使计算更快,我可以使用循环中的平方距离并在结尾返回根.

这种方法的运行时复杂度为 n列表的长度在哪里L.(并且空间复杂度不变).

凸壳

显然,不能有任何比O(n)更快的算法,因为必须在列表中的每个元素上至少查看一次.

最高距离将在凸包的元件之间.但是很容易证明凸包的计算至少在这里,O(n log n)并且格雷厄姆的扫描似乎就是这样做的.但在找到复杂的船体后,我仍然需要获得最大距离.所以我最终会结束

def find_max_dist_graham_triv(L):
    H = Graham_scan(L)
    return find_max_dist(L)

现在,这是我不确定的一点.我认为可以这样改进:

def find_max_dist_graham_c1(L):
    H = Graham_scan(L)  # Get ordered list of convex hull points
    max_dist = d(L[0], L[1])
    for i in range(0, len(L)-1):
        loop_max_dist = 0
        for j in range(i+1, len(L):
            curr_dist = d(L[i], L[j])
            if curr_dist < loop_max_dist:
                break
            loop_max_dist = curr_dist
            max_dist = max(loop_max_dist, max_dist)

    return max_dist

这个想法是,当你从一个凸包的一个点开始并从它的相邻点开始时,对角线不断增加,达到最大值然后继续减小.不过,我不确定这是否属实.

直觉上,我会继续改进算法:一旦第一个内循环结束,我们就找到了该循环的"最长对角线".该对角线将两个分离集中的所有其他船体点分开.每个较长的对角线必须由这两组中的点组成(正确吗？):

def find_max_dist_graham_c1(L):
    H = Graham_scan(L)  # Get ordered list of convex hull points
    max_dist = d(L[0], L[1])  # Get a fist idea what the longest distance might be

    i = 0
    p1 = L[i]  # Grab a random point
    loop_max_dist = 0
    for j in range(1, len(L):
        curr_dist = d(L[i], L[j])
        if curr_dist < loop_max_dist:
            break
        loop_max_dist = curr_dist
        max_dist = max(loop_max_dist, max_dist)
    # Every diagonal that is longer than the best one found with L[0]
    # has to have points in both of the following two sets (correct?):
    # [1...j] and [j+1...len(L)]

    # Try to find a neighboring diagonal that is longer.
    change = True
    while change:
        change = False
        if d(L[i-1], L[j+1]) > max_dist:
            max_dist = d(L[i-1], L[j+1])
            i -= 1
            j += 1
            change = True
        elif d(L[i+1], L[j-1]) > max_dist:
            max_dist = d(L[i+1], L[j-1])
            i += 1
            j -= 1
            change = True
    return max_dist

凸包上的每个点P在凸包上都有一个点Q,使得PQ是包括P的最长对角线.但是,P也是Q的最长对角线的"终点"？

我真的不确定这个算法是否正确.它将在O(n log n)中.

我想这个问题已得到很好的分析,所以有人可以留下一些注意事项吗？

虽然我有很多子问题但主要问题是:

找到点列表中点的最大距离的有效方法是什么？

Answer 1

你应该查看Rotating calipers(http://en.wikipedia.org/wiki/Rotating_calipers) - 它们被广泛用于那种问题.而且,你的假设是错误的.对于凸多边形上的固定点p:对角线可以先增加,然后减小,然后增加,然后再减小.至少,我有一个发生这种情况的案例.

启发式方法也是:选择一个点x.从中找出最远点y.从y找到最远点z.d(z,y)是一个很好的估计.

说明对角线的图像:

1-> 2:增加; 2-> 3减少; 3-> 4增加; 4-> 5减少.该图可能不精确,将点3和4指向远离p的点(在同一条线上).