计算列表中两点最大距离的最有效方法是什么? [英] What is the most efficient way to calculate the maximum distance of two points in a list?

问题描述

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

I have a list L of points (x, y) and the usual euclidean distance measure

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

How do I find the maximum distance two points have in this list? Or, more formally: How do I find

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

The simplest way to solve this problem seems to be to try everything:

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

为了使计算更快，我可以在循环中使用平方距离并在最后返回根.

To make computation faster, I can use the squared distance in the loops and return the root at the end.

这种方法的运行时间复杂度为 其中 n 是列表 L 的长度.(以及恒定的空间复杂度).

This approach has a run time complexity of where n is the lenght of the list L. (And a constant space complexity).

显然，没有任何算法比 O(n) 更快，因为我们必须对列表中的每个元素至少查看一次.

Obviously, there cannot be any algorithm that is faster than O(n), as one has to look at least once at every element in the list.

凸包元素之间的距离最大.但是很容易证明凸包的计算至少在 O(n log n) 和 Graham 的扫描 似乎可以做到.但是在找到复杂的船体之后，我仍然必须获得最大距离.所以我最终会得到

The highest distance will be between elements of the convex hull. But it is easy to prove that the computation of the convex hull is at least in O(n log n) and Graham's scan seems to do it. But after finding the complex hull I still have to get the maximum distance. So I would end up with

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

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

Now, this is a point where I am not sure. I think one can improve this like so:

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

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

The idea is that when you take one point of a convex hull and start from its neighboring point, the diagonals keep increasing, get to a maximum and then keep decreasing. I'm not sure if this is true, though.

直观地说，我会继续改进算法:一旦第一个内部循环完成，我们就找到了该循环的最长对角线".这条对角线将所有其他船体点分隔成两个分离的集合.每条较长的对角线都必须由这两个集合中的点组成(对吗?):

Intuitively, I would continue to improve the algorithm: As soon as the first inner loop finishes, we found a "longest diagonal" of that loop. This diagonal separates all other hull points in two disjunct sets. Every longer diagonal has to consist of points from both of those sets (correct?):

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 的最长对角线的端点"吗?

Every point P on the convex hull has a point Q on the convex hull such that PQ is the longest diagonal including P. But is then P also the "endpoint" for the longest diagonal of Q?

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

I am really not sure if this algorithm is correct. It would be in O(n log n).

我想这个问题分析得很好，所以有人可以留下一些笔记吗?

I guess the problem is well analyzed, so could somebody please leave some notes for that?

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

Although I had a lot of sub-questions the main question is:

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

推荐答案

你应该看看旋转卡尺(http://en.wikipedia.org/wiki/Rotating_calipers)——它们被广泛用于这类问题.另外，你的假设是错误的.对于凸多边形上的一个不动点p:对角线可以先增减，再增减.至少，我有一个发生这种情况的案例.

You should look up on Rotating calipers(http://en.wikipedia.org/wiki/Rotating_calipers) - they're widely used for that kind of problems. Also, your assumption is wrong. For a fixed point p on the convex polygon: the diagonal can first increase, then decrease, then increase, and then decrease again. At least, I've got a case where this happens.

还有一种启发式方法:选择一个点 x.找到离它最远的点y.找到距离 y 最远的点 z.d(z,y) 是一个很好的估计.

A heuristic approach also: select a point x. Find the furthest point y from it. Find the furthest point z from y. d(z,y) is a good estimation.

说明对角线的图像:

1->2:增加；2->3 递减；3->4 增加；4->5 递减.图可能不准确，把3和4指向的点移到离p远一点(在同一条线上).

1->2: increasing; 2->3 decreasing; 3->4 increasing; 4->5 decreasing. The figure may not be precise, move the points that 3 and 4 point to a bit further away from p (on the same line).

这篇关于计算列表中两点最大距离的最有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！