Closest Pair of Points — Divide and Conquer O(n log n)

The closest pair problem is a beautiful example of computational geometry enabling an otherwise-quadratic combine step to run in linear time. The naive O(n^2) solution checks every pair. The D&C solution achieves O(n log n) by proving a remarkable geometric fact: in the critical 'strip' around the dividing line, each point has at most 7 other points it needs to check.

This seven-point bound — derived from packing arguments in a 2δ×δ rectangle — is the kind of geometric reasoning that separates algorithm designers from algorithm users. It is also a template for many computational geometry optimisations: use the structure of space to bound the number of interactions.

Algorithm Overview

1. Sort points by x-coordinate: O(n log n)
2. Recursively find closest pair in left half (δ_L) and right half (δ_R)
3. δ = min(δ_L, δ_R)
4. Find all points within δ of the dividing line (the strip)
5. Check pairs in the strip sorted by y-coordinate
6. The key: each point in the strip has at most 7 other points to check

from math import dist
from itertools import combinations

def closest_pair(points: list[tuple]) -> tuple[float, tuple, tuple]:
    points = sorted(points, key=lambda p: p[0])
    return _closest(points)

def _closest(pts):
    n = len(pts)
    if n <= 3:
        # Brute force for small input
        best = float('inf'), pts[0], pts[1]
        for a, b in combinations(pts, 2):
            d = dist(a, b)
            if d < best[0]: best = d, a, b
        return best
    mid = n // 2
    mid_x = pts[mid][0]
    d_left  = _closest(pts[:mid])
    d_right = _closest(pts[mid:])
    best = d_left if d_left[0] < d_right[0] else d_right
    delta = best[0]
    # Build strip: points within delta of dividing line
    strip = [p for p in pts if abs(p[0] - mid_x) < delta]
    strip.sort(key=lambda p: p[1])  # sort by y
    # Check strip pairs (at most 7 comparisons per point)
    for i in range(len(strip)):
        for j in range(i+1, min(i+8, len(strip))):
            if strip[j][1] - strip[i][1] >= delta:
                break
            d = dist(strip[i], strip[j])
            if d < delta:
                best = d, strip[i], strip[j]
                delta = d
    return best

points = [(2,3),(12,30),(40,50),(5,1),(12,10),(3,4)]
d, p1, p2 = closest_pair(points)
print(f'Closest: {p1} and {p2}, distance: {d:.4f}')

The '7 Neighbours' Proof

Why does each point in the strip have at most 7 other points to check? Consider a δ×2δ rectangle straddling the midline. In each δ×δ half, the closest pair distance is ≥ δ (we already found the best in each half). So in each δ×δ quarter, we can pack at most 4 points at distance ≥ δ from each other (a 2×2 grid). Total: 8 points maximum in the 2δ×2δ strip rectangle including the reference point itself — so at most 7 others.

This bounds the inner loop to constant work per point → O(n) combine step.

Optimisation — Pre-Sort by Y

Re-sorting the strip each time adds a log factor. The optimisation: maintain two sorted arrays throughout — one sorted by x (for dividing) and one sorted by y (for strip checking). This gives T(n) = 2T(n/2) + O(n) → O(n log n) with smaller constants.

Frequently Asked Questions