Closest Pair of Points Demo

def closest_pair_brute_force(points):
    """
    Brute force: check all pairs.
    Time: O(n²), Space: O(1)
    """
    min_dist = float('inf')
    closest = None
    
    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            dist = distance(points[i], points[j])
            if dist < min_dist:
                min_dist = dist
                closest = (points[i], points[j])
    
    return closest, min_dist

def distance(p1, p2):
    return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)**0.5

def closest_pair(points):
    """
    Closest pair using divide & conquer.
    Time: O(n log² n), Space: O(n)
    """
    # Sort by x-coordinate
    points_sorted = sorted(points, key=lambda p: p[0])
    return closest_pair_rec(points_sorted)

def closest_pair_rec(points):
    n = len(points)
    
    # Base case
    if n <= 3:
        return closest_pair_brute_force(points)
    
    # Divide
    mid = n // 2
    mid_point = points[mid]
    
    left_points = points[:mid]
    right_points = points[mid:]
    
    # Conquer
    left_closest, left_dist = closest_pair_rec(left_points)
    right_closest, right_dist = closest_pair_rec(right_points)
    
    # Find minimum of two halves
    min_dist = min(left_dist, right_dist)
    closest = left_closest if left_dist < right_dist else right_closest
    
    # Combine: Check strip
    strip = []
    for point in points:
        if abs(point[0] - mid_point[0]) < min_dist:
            strip.append(point)
    
    # Sort strip by y-coordinate
    strip.sort(key=lambda p: p[1])
    
    # Check points in strip
    for i in range(len(strip)):
        j = i + 1
        while j < len(strip) and (strip[j][1] - strip[i][1]) < min_dist:
            dist = distance(strip[i], strip[j])
            if dist < min_dist:
                min_dist = dist
                closest = (strip[i], strip[j])
            j += 1
    
    return closest, min_dist

def closest_pair_optimized(points):
    """
    Optimized closest pair: O(n log n)
    """
    # Sort by x and y coordinates
    points_x = sorted(points, key=lambda p: p[0])
    points_y = sorted(points, key=lambda p: p[1])
    
    return closest_pair_rec_optimized(points_x, points_y)

def closest_pair_rec_optimized(points_x, points_y):
    n = len(points_x)
    
    if n <= 3:
        return closest_pair_brute_force(points_x)
    
    mid = n // 2
    mid_point = points_x[mid]
    
    # Divide points_y into left and right
    left_y = [p for p in points_y if p[0] <= mid_point[0]]
    right_y = [p for p in points_y if p[0] > mid_point[0]]
    
    # Conquer
    left_closest, left_dist = closest_pair_rec_optimized(
        points_x[:mid], left_y)
    right_closest, right_dist = closest_pair_rec_optimized(
        points_x[mid:], right_y)
    
    min_dist = min(left_dist, right_dist)
    closest = left_closest if left_dist < right_dist else right_closest
    
    # Strip
    strip = [p for p in points_y if abs(p[0] - mid_point[0]) < min_dist]
    
    # Check strip (at most 6 points per point)
    for i in range(len(strip)):
        j = i + 1
        while j < len(strip) and (strip[j][1] - strip[i][1]) < min_dist:
            dist = distance(strip[i], strip[j])
            if dist < min_dist:
                min_dist = dist
                closest = (strip[i], strip[j])
            j += 1
    
    return closest, min_dist