作业求助：求二维平面最远点对的O(nlogn)高效算法

Hey there! I get that hunting for a farthest-point-pair algorithm when all you find is closest-pair stuff can be frustrating. Let's break this down into a straightforward, assignment-friendly solution that hits your O(nlogn) complexity goal.

The Key Insight: Farthest Points Lie on the Convex Hull #

First off, a critical observation: the two farthest points in any 2D point set must lie on the convex hull of the set. The convex hull is like the "outer boundary" of points—any point inside this boundary can't be part of the farthest pair, because you'd get a longer distance by using points on the hull instead.

So our plan has two main steps:

• Compute the convex hull of your point set (O(nlogn) time)
• Use the "rotating calipers" technique to find the farthest pair on the convex hull (O(m) time, where m is the number of points on the hull—m ≤ n, so this keeps the total complexity O(nlogn))

Step 1: Compute the Convex Hull (Andrew's Monotone Chain Algorithm) #

Andrew's algorithm is one of the easiest convex hull methods to implement, and it runs in O(nlogn) time thanks to sorting. Here's how it works:

• Sort all points by their x-coordinate (and y-coordinate if x's are equal)
• Build the lower hull: iterate through sorted points, removing points that would create a non-left turn (using cross product to check direction)
• Build the upper hull: iterate through sorted points in reverse, doing the same non-left turn check
• Combine the lower and upper hulls (excluding duplicate endpoints) to get the full convex hull

Step 2: Rotating Calipers for Farthest Pair #

Once you have the convex hull (a convex polygon), rotating calipers lets you find the farthest pair in linear time. The idea is:

• For each edge of the convex hull, find the vertex farthest from that edge
• Track the maximum distance between any such vertex-edge pair (this corresponds to the farthest point pair)

Since the hull is convex, you can traverse it with two pointers, moving one pointer as you iterate through the other—no need to check every possible pair (which would be O(m²) time).

Full Example Code (Python) #

Here's a clean, commented implementation that you can adapt for your needs:

def find_farthest_pair(points):
    # Helper function: Calculate cross product to determine turn direction
    def cross(o, a, b):
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
    
    # Helper function: Calculate squared distance (avoids sqrt for efficiency)
    def squared_distance(a, b):
        return (a[0] - b[0])**2 + (a[1] - b[1])**2

    # Step 1: Compute convex hull using Andrew's monotone chain algorithm
    points = sorted(points)
    lower_hull = []
    for p in points:
        # Remove points that cause a non-left turn
        while len(lower_hull) >= 2 and cross(lower_hull[-2], lower_hull[-1], p) <= 0:
            lower_hull.pop()
        lower_hull.append(p)
    
    upper_hull = []
    for p in reversed(points):
        # Remove points that cause a non-left turn
        while len(upper_hull) >= 2 and cross(upper_hull[-2], upper_hull[-1], p) <= 0:
            upper_hull.pop()
        upper_hull.append(p)
    
    # Combine hulls (exclude duplicate first/last points)
    convex_hull = lower_hull[:-1] + upper_hull[:-1]
    m = len(convex_hull)
    
    # Edge cases: 1 or 2 points
    if m == 1:
        return (convex_hull[0], convex_hull[0])
    if m == 2:
        return (convex_hull[0], convex_hull[1])

    # Step 2: Rotating calipers to find farthest pair
    max_dist_sq = -1
    best_pair = (None, None)
    j = 1  # Start with the next point after i=0

    for i in range(m):
        i_next = (i + 1) % m
        # Move j to the farthest point from edge (i, i_next)
        while True:
            j_next = (j + 1) % m
            # Compare area of triangles (area = 0.5 * base * height, so area correlates with distance)
            current_area = cross(convex_hull[i], convex_hull[i_next], convex_hull[j])
            next_area = cross(convex_hull[i], convex_hull[i_next], convex_hull[j_next])
            if next_area > current_area:
                j = j_next
            else:
                break
        # Update max distance pair
        current_dist_sq = squared_distance(convex_hull[i], convex_hull[j])
        if current_dist_sq > max_dist_sq:
            max_dist_sq = current_dist_sq
            best_pair = (convex_hull[i], convex_hull[j])
    
    return best_pair

# Example usage
if __name__ == "__main__":
    sample_points = [(0,0), (1,1), (2,3), (5,4), (3,0), (4,5)]
    p1, p2 = find_farthest_pair(sample_points)
    print(f"The farthest pair of points is: {p1} and {p2}")

Why This Works for Your Assignment #

• Complexity Check: Sorting takes O(nlogn), convex hull construction is O(n), rotating calipers is O(m) ≤ O(n). Total time is O(nlogn), which meets your goal.
• Simplicity: Compared to the overly complex solution you found, this approach is modular and easy to explain/implement—perfect for homework.
• Correctness: The convex hull guarantee ensures we don't miss any potential farthest pairs, and rotating calipers efficiently finds the maximum pair on the hull.

内容的提问来源于stack exchange，提问作者user12269498