凸包中任意两点间的最大距离

Question

我正在解决一个问题，需要在平面上（2D）找到两点之间的最大距离。有一种O（n ^ 2）方法，我计算图中每个点之间的距离。我还实现了凸包算法，现在我的方法是先以O（nlogn）的时间复杂度计算凸包，然后使用O（n ^ 2）算法计算凸包中点之间的最大距离。是否有比这更好的方法来计算凸包中的最大距离？

以下是我的算法：

O(n^2)

 def d(l1,l2):
    return ((l2[0]-l1[0])**2+(l2[1]-l1[1])**2)
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

凸包

def convex_hull(points):
    """Computes the convex hull of a set of 2D points.

       Input: an iterable sequence of (x, y) pairs representing the points.
       Output: a list of vertices of the convex hull in counter-clockwise order,
       starting from the vertex with the lexicographically smallest coordinates.
       Implements Andrew's monotone chain algorithm. O(n log n) complexity.
"""

      # Sort the points lexicographically (tuples are compared lexicographically).
      # Remove duplicates to detect the case we have just one unique point.
        points = sorted(set(points))

      # Boring case: no points or a single point, possibly repeated multiple times.
    if len(points) <= 1:
        return points

    # 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
    # Returns a positive value, if OAB makes a counter-clockwise turn,
    # negative for clockwise turn, and zero if the points are collinear.
    def cross(o, a, b):
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

    # Build lower hull
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    # Build upper hull
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    # Concatenation of the lower and upper hulls gives the convex hull.
    # Last point of each list is omitted because it is repeated at the beginning of the other list.
    return lower[:-1] + upper[:-1]

整体算法

 l=[]
 for i in xrange(int(raw_input())):   # takes input denoting number  of points in the plane
     n=tuple(int(i) for i in raw_input().split())  #takes each point and makes a tuple
     l.append(n)                                # appends to n

 if len(l)>=10:
        print find_max_dist(convex_hull(l))
 else:
        print find_max_dist(l)

现在怎样改进我的方法的运行时间？是否有更好的计算方法？

- sid597

---

你考虑过旋转卡壳算法吗？ - Jacob Panikulam

@JacobPanikulam 不行，它能用来计算一组点的直径吗？ - sid597

是的。如果我理解你的问题，这是一个线性时间的解决方案。 - Jacob Panikulam

Answer 1

一旦您有一个凸包，您可以在线性时间内找到两个最远的点。

思路是保持两个指针：其中一个指向当前边缘（并且始终增加一个），另一个指向一个顶点。

答案是所有边缘的端点和顶点之间的最大距离。

可以证明（证明不短，也不平凡，因此我不会在这里发布）如果我们在移动第一个指针后每次将第二个指针增加，只要它增加了通过边缘和顶点的线之间的距离，我们将找到最佳答案。

- kraskevich