Closest Pair of Points

Given a set of points on a plane, find the two that are closest together. Testing every pair is the obvious move, but it costs O(n^2). The closest pair of points algorithm uses divide & conquer to get the answer in O(n log n) — and the clever part is a thin vertical strip that lets it skip almost every cross-boundary comparison.

For the six points p0..p5 on the right (already sorted by x), the left half p0, p1, p2 has best distance about 22.6, the right half p3, p4, p5 about 24.1, so d = 22.6. The strip around the split holds only p2, p3, whose distance 27.2 does not beat d — so the closest pair is (p0, p1).

Intuition

Why does the strip work? After solving both halves we already know no pair within a half is closer than d. The only pairs left to worry about are ones with one point on each side of the line. But if a point is farther than d from the line horizontally, even its x-gap alone already exceeds d — it can never form a closer pair across the divide. So we can throw away everything except the band of width 2d hugging the split line.

Inside that strip there is a second magic fact: if you sort the strip points by y, each point only needs to be compared with a constant number of the points just above it (at most 7). Geometry guarantees that no more than a handful of points can be packed into a d-by-2d box without two of them being closer than d — which would contradict what we already computed. That bounded inner loop is what keeps the merge step linear.

Walk through it

Step through the animation on the right.

First the six points appear, sorted left to right by x. A vertical split line drops at the median x, separating p0, p1, p2 from p3, p4, p5.

Now we recurse. The left half lights up and reports its closest pair (p0, p1) at 22.6; the right half reports (p3, p4) at 24.1. We take d = min(22.6, 24.1) = 22.6.

Next the strip of width 2d appears around the line. Only p2 and p3 fall inside it — every other point is more than d from the split, so it cannot help. We sort the strip by y and run the limited cross-check: d(p2, p3) = 27.2, which is bigger than 22.6, so nothing improves. The final answer stays (p0, p1) with distance 22.6, drawn as the connecting edge.

The code, line by line

def closest_pair(pts):
    pts = sorted(pts, key=lambda p: p[0])  # sort by x
    return _rec(pts)
 
def _rec(P):
    if len(P) <= 3:
        return min(dist(a, b) for a, b in pairs(P))
    mid = len(P) // 2
    midx = P[mid][0]
    dl = _rec(P[:mid])                # left half
    dr = _rec(P[mid:])                # right half
    d = min(dl, dr)
    strip = [p for p in P if abs(p[0] - midx) < d]
    strip.sort(key=lambda p: p[1])    # sort strip by y
    for i in range(len(strip)):
        for j in range(i + 1, min(i + 8, len(strip))):
            d = min(d, dist(strip[i], strip[j]))
    return d

• The one-time sorted by x (line 2) is what lets every recursive split just take a left and right slice of the list.
• The base case (lines 6–7) brute-forces groups of ≤ 3 points — for tiny sets O(n^2) is fine and avoids fiddly recursion.
• Lines 10–12 solve the two halves and set d to the better of them — the candidate answer before we consider any straddling pair.
• Line 13 builds the strip: keep only points whose x is within d of the split line. Everything else is provably too far to beat d.
• Line 14 sorts the strip by y so that close-by candidates are adjacent in the list.
• Lines 15–16 are the bounded cross-check: for each strip point look at most 7 ahead (min(i + 8, ...)). That constant cap is what keeps the merge O(n), not O(n^2).

Complexity

The recurrence is the same shape as merge sort: two half-size subproblems plus a linear-time merge (the strip scan). That solves to O(n log n). Without the strip trick, comparing every left point against every right point would make the merge O(n^2) and sink the whole thing back to brute force.

When to use / pitfalls

Practice