Introduction
The closest pair of points problem asks: given n points in a plane, find the pair with the smallest Euclidean distance between them. A brute-force approach checks all pairs in O(n^2) time. Divide and conquer reduces this to O(n log n) by splitting the points into left and right halves, recursively finding the closest pair in each half, and then carefully checking a narrow 'strip' near the dividing line for any closer cross-boundary pair.
Cricket analogy: Comparing every pair of fielders' positions to find the two standing closest is like brute-force checking every batting pair for the best partnership; splitting the ground into off-side and leg-side halves and only rechecking near the crease line is the divide-and-conquer shortcut.
Algorithm/Syntax
import math
def closest_pair(points):
points_x = sorted(points, key=lambda p: p[0])
points_y = sorted(points, key=lambda p: p[1])
return _closest_pair_rec(points_x, points_y)
def _closest_pair_rec(px, py):
n = len(px)
if n <= 3:
return brute_force(px)
mid = n // 2
mid_point = px[mid]
left_x, right_x = px[:mid], px[mid:]
left_set = set(map(tuple, left_x))
left_y = [p for p in py if tuple(p) in left_set]
right_y = [p for p in py if tuple(p) not in left_set]
d_left = _closest_pair_rec(left_x, left_y)
d_right = _closest_pair_rec(right_x, right_y)
d = min(d_left, d_right)
strip = [p for p in py if abs(p[0] - mid_point[0]) < d]
d_strip = strip_closest(strip, d)
return min(d, d_strip)Explanation
The points are pre-sorted by x-coordinate (px) and y-coordinate (py) once, before recursion begins, to avoid repeated sorting. The divide step splits px at the median x-coordinate into left and right halves, while preserving y-sorted order for each half (left_y, right_y) using a set membership check. The conquer step recursively computes the minimum distance d_left and d_right within each half. The combine step is the interesting part: any pair straddling the dividing line and closer than d = min(d_left, d_right) must lie within a vertical strip of width 2d centered on the dividing line, so only points within that strip need to be checked, and a classic geometric argument shows that for each point in the strip, only the next 7 points (when sorted by y) need to be compared.
Cricket analogy: Sorting fielders once by their position along the boundary rope before the over starts, then during the strip check near the crease only comparing a batsman against the next 7 nearby fielders, avoids resorting every ball.
Example
import math
def dist(p1, p2):
return math.hypot(p1[0] - p2[0], p1[1] - p2[1])
def brute_force(points):
min_d = float('inf')
n = len(points)
for i in range(n):
for j in range(i + 1, n):
min_d = min(min_d, dist(points[i], points[j]))
return min_d
def strip_closest(strip, d):
strip.sort(key=lambda p: p[1])
min_d = d
n = len(strip)
for i in range(n):
j = i + 1
while j < n and (strip[j][1] - strip[i][1]) < min_d:
min_d = min(min_d, dist(strip[i], strip[j]))
j += 1
return min_d
def closest_pair(points):
points_x = sorted(points, key=lambda p: p[0])
points_y = sorted(points, key=lambda p: p[1])
return _closest_pair_rec(points_x, points_y)
def _closest_pair_rec(px, py):
n = len(px)
if n <= 3:
return brute_force(px)
mid = n // 2
mid_point = px[mid]
left_x, right_x = px[:mid], px[mid:]
left_set = set(map(tuple, left_x))
left_y = [p for p in py if tuple(p) in left_set]
right_y = [p for p in py if tuple(p) not in left_set]
d_left = _closest_pair_rec(left_x, left_y)
d_right = _closest_pair_rec(right_x, right_y)
d = min(d_left, d_right)
strip = [p for p in py if abs(p[0] - mid_point[0]) < d]
d_strip = strip_closest(strip, d)
return min(d, d_strip)
# Points include a close pair (2,3) and (3,4) at distance sqrt(2) ~ 1.414
pts = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(round(closest_pair(pts), 3)) # 1.414Complexity
The recurrence is T(n) = 2T(n/2) + O(n), where the O(n) term comes from building the strip and scanning it (each point compared against at most 7 neighbors due to a packing argument on minimum pairwise distances), rather than the naive O(n log n) strip sort per level. This resolves to O(n log n) overall, a major improvement over the O(n^2) brute-force approach. The initial sort of points by x and y coordinates also takes O(n log n), matching the recursive part's complexity, so the total remains O(n log n).
Cricket analogy: Splitting a tournament's fixture analysis into two halves recursively, then spending only linear time scanning each match day's strip of close finishes (never rechecking more than 7 games), keeps total analysis at O(n log n), same cost as the initial seeding sort.
Key Takeaways
- The closest pair of points problem is solved in O(n log n) using divide and conquer, versus O(n^2) for brute force.
- Points are split into left and right halves by x-coordinate, with the closest pair found recursively in each half.
- The combine step checks a narrow strip around the dividing line for any closer cross-boundary pair, exploiting a geometric bound of at most 7 comparisons per point.
- Maintaining y-sorted order across recursive calls without re-sorting at each level keeps the combine step at O(n), giving the overall T(n) = 2T(n/2) + O(n) recurrence.
Practice what you learned
1. What is the time complexity of the divide-and-conquer closest pair of points algorithm?
2. What is the purpose of the 'strip' in the combine step of the closest pair algorithm?
3. Why does each point in the strip only need to be compared against at most 7 subsequent points (sorted by y)?
4. Why is it important to maintain y-sorted order across recursive calls rather than re-sorting at each level?
Was this page helpful?
You May Also Like
The Divide and Conquer Paradigm
Learn how divide, conquer, and combine steps break large problems into smaller solvable subproblems.
Merge Sort as Divide and Conquer
See how merge sort applies divide, conquer, and combine to achieve guaranteed O(n log n) sorting.
The Master Theorem
Apply the Master Theorem's three cases to quickly solve divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n).
Recursion Trees and Recurrence Relations
Model the runtime of recursive algorithms as recurrence relations and solve them by drawing recursion trees.