Common Divide and Conquer Patterns

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import math
from typing import List, Tuple
 
Point = Tuple[float, float]
 
def euclidean_distance(p1: Point, p2: Point) -> float:
    """Calculate Euclidean distance between two points."""
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
 
def brute_force_closest_pair(points: List[Point]) -> Tuple[Point, Point, float]:
    """
    Find closest pair using brute force.
    Time Complexity: O(n²)
    Space Complexity: O(1)
    
    Returns: (point1, point2, distance)
    """
    n = len(points)
    if n < 2:
        raise ValueError("Need at least 2 points")
    
    min_distance = float('inf')
    closest_pair = (points[0], points[1])
    
    # Check all pairs: n*(n-1)/2 pairs total
    for i in range(n):
        for j in range(i + 1, n):
            d = euclidean_distance(points[i], points[j])
            if d < min_distance:
                min_distance = d
                closest_pair = (points[i], points[j])
    
    return closest_pair[0], closest_pair[1], min_distance
 
# Example usage
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
p1, p2, dist = brute_force_closest_pair(points)
print(f"Closest pair: {p1}, {p2}")
print(f"Distance: {dist:.4f}")
# Output: Closest pair: (2, 3), (3, 4)
# Distance: 1.4142

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

def process_strip(strip: List[Point], delta: float) -> float:
    """
    Process the strip to find closer pairs.
    
    The strip is sorted by y-coordinate.
    For each point, we only need to check the next 7 points
    due to the geometric packing argument.
    
    Time Complexity: O(n) - each point compared with at most 7 others
    """
    n = len(strip)
    min_dist = delta  # We're looking for pairs closer than delta
    closest = None
    
    for i in range(n):
        # Only check the next 7 points (j = i+1 to min(i+8, n))
        # The y-distance condition is implicit in the bound,
        # but we add it for clarity and minor optimization
        j = i + 1
        while j < n and j < i + 8:  # At most 7 comparisons
            # Additional pruning: if y-distance > delta, skip remaining
            if strip[j][1] - strip[i][1] >= min_dist:
                break
            
            d = euclidean_distance(strip[i], strip[j])
            if d < min_dist:
                min_dist = d
                closest = (strip[i], strip[j])
            j += 1
    
    return min_dist, closest
 
 
def process_strip_with_proof(strip: List[Point], delta: float) -> float:
    """
    Alternative implementation that explicitly shows the geometric proof.
    We check points in a 2δ × δ rectangle above each point.
    
    This version is more intuitive but equivalent to checking 7 points.
    """
    n = len(strip)
    min_dist = delta
    closest = None
    
    for i in range(n):
        for j in range(i + 1, n):
            # Key insight: if y-difference exceeds delta, 
            # distance cannot be less than delta
            if strip[j][1] - strip[i][1] >= delta:
                break  # All subsequent points are farther in y
            
            d = euclidean_distance(strip[i], strip[j])
            if d < min_dist:
                min_dist = d
                closest = (strip[i], strip[j])
    
    return min_dist, closest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

import math
from typing import List, Tuple, Optional
 
Point = Tuple[float, float]
 
def euclidean_distance(p1: Point, p2: Point) -> float:
    """Calculate Euclidean distance between two points."""
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
 
def brute_force(points: List[Point]) -> Tuple[float, Optional[Tuple[Point, Point]]]:
    """
    Brute force for small inputs (base case).
    Used when n ≤ 3.
    """
    min_dist = float('inf')
    closest = None
    n = len(points)
    
    for i in range(n):
        for j in range(i + 1, n):
            d = euclidean_distance(points[i], points[j])
            if d < min_dist:
                min_dist = d
                closest = (points[i], points[j])
    
    return min_dist, closest
 
def closest_pair_dc(points: List[Point]) -> Tuple[float, Tuple[Point, Point]]:
    """
    Find the closest pair of points using Divide and Conquer.
    
    Time Complexity: O(n log n)
        - Preprocessing sort: O(n log n)
        - Each recursion level: O(n) work
        - log n recursion levels
    
    Space Complexity: O(n) for the recursive call stack and sorted arrays
    
    Args:
        points: List of (x, y) coordinate tuples
        
    Returns:
        Tuple of (distance, (point1, point2))
    """
    n = len(points)
    if n < 2:
        raise ValueError("Need at least 2 points")
    
    # Pre-sort by x-coordinate (done once, O(n log n))
    points_sorted_x = sorted(points, key=lambda p: (p[0], p[1]))
    # Pre-sort by y-coordinate (for strip processing)
    points_sorted_y = sorted(points, key=lambda p: (p[1], p[0]))
    
    return _closest_pair_recursive(points_sorted_x, points_sorted_y)
 
def _closest_pair_recursive(
    px: List[Point],  # Points sorted by x
    py: List[Point]   # Points sorted by y
) -> Tuple[float, Optional[Tuple[Point, Point]]]:
    """
    Recursive helper for closest pair.
    
    Maintains both x-sorted and y-sorted lists to avoid
    re-sorting at each level (key optimization).
    """
    n = len(px)
    
    # Base case: use brute force for small inputs
    if n <= 3:
        return brute_force(px)
    
    # ============ DIVIDE ============
    mid = n // 2
    mid_point = px[mid]
    mid_x = mid_point[0]
    
    # Split x-sorted points
    px_left = px[:mid]
    px_right = px[mid:]
    
    # Split y-sorted points while maintaining y-order
    # This is O(n) instead of re-sorting
    py_left = []
    py_right = []
    left_set = set(px_left)  # O(n) to build
    
    for point in py:
        if point in left_set:
            py_left.append(point)
        else:
            py_right.append(point)
    
    # ============ CONQUER ============
    dist_left, pair_left = _closest_pair_recursive(px_left, py_left)
    dist_right, pair_right = _closest_pair_recursive(px_right, py_right)
    
    # Find minimum from recursive calls
    if dist_left < dist_right:
        delta = dist_left
        closest_pair = pair_left
    else:
        delta = dist_right
        closest_pair = pair_right
    
    # ============ COMBINE ============
    # Build the strip: points within delta of the dividing line
    # Using py (y-sorted) so strip is automatically y-sorted
    strip = [p for p in py if abs(p[0] - mid_x) < delta]
    
    # Process the strip - O(n) due to the constant bound
    strip_dist, strip_pair = process_strip_optimized(strip, delta)
    
    if strip_pair and strip_dist < delta:
        return strip_dist, strip_pair
    
    return delta, closest_pair
 
def process_strip_optimized(
    strip: List[Point], 
    delta: float
) -> Tuple[float, Optional[Tuple[Point, Point]]]:
    """
    Process the strip to find pairs closer than delta.
    
    The strip is already sorted by y-coordinate.
    Due to the packing argument, we check at most 7 subsequent points.
    
    Time Complexity: O(n) - not O(n²) despite nested loop
    """
    min_dist = delta
    closest = None
    n = len(strip)
    
    for i in range(n):
        # Check at most 7 subsequent points
        for j in range(i + 1, min(i + 8, n)):
            # Early termination: if y-distance >= min_dist, break
            if strip[j][1] - strip[i][1] >= min_dist:
                break
            
            d = euclidean_distance(strip[i], strip[j])
            if d < min_dist:
                min_dist = d
                closest = (strip[i], strip[j])
    
    return min_dist, closest
 
 
# ============ DEMONSTRATION ============
if __name__ == "__main__":
    # Test with known closest pair
    test_points = [
        (2, 3), (12, 30), (40, 50), (5, 1), 
        (12, 10), (3, 4), (0, 0), (100, 100)
    ]
    
    dist, (p1, p2) = closest_pair_dc(test_points)
    print(f"Points: {test_points}")
    print(f"Closest pair: {p1}, {p2}")
    print(f"Distance: {dist:.6f}")
    
    # Verify with brute force
    bf_dist, bf_pair = brute_force(test_points)
    print(f"
Brute force verification:")
    print(f"Closest pair: {bf_pair}")
    print(f"Distance: {bf_dist:.6f}")
    print(f"Match: {abs(dist - bf_dist) < 1e-9}")