Divide & Conquer8 min read

Closest Pair of Points

Find the two nearest cities on a map — without measuring every pair
naive:Slow · \(O(n^2)\)divide & conquer:Fast · \(O(n \log n)\)space:Linear · \(O(n)\)

Imagine you have a map with hundreds of cities scattered across it, and you want to find the two closest cities. The lazy approach: measure every possible pair. With 1,000 cities that's 500,000 measurements. With a million cities? Half a trillion. Way too slow.

The smart approach uses divide and conquer — splits the map in half, solves each half separately, then cleverly merges — and it finishes in \(O(n \log n)\) time, the same speed as sorting. Here's how.

The Naive Way — \(O(n^2)\)

Check every pair (i, j) and keep track of the shortest distance seen. Simple, correct, and painfully slow for large inputs. We need something smarter.

Divide & Conquer — the Big Idea

Step 1 — Divide: Sort all points by x-coordinate. Draw a vertical line through the median, splitting the set into a left half L and a right half R.

Step 2 — Conquer: Recursively find the closest pair in L (distance δ_L) and in R (distance δ_R). Let δ = min(δ_L, δ_R). We now know the best answer within each half.

Step 3 — Combine: Can a pair that straddles the dividing line beat δ? Only if both points are within δ of the line — otherwise their horizontal gap alone exceeds δ. This thin vertical strip is all we need to check.

The Magic of the Strip — Why Only 7 Neighbors?

Consider the strip: points within distance δ of the dividing line, sorted by y-coordinate. Within any δ × 2δ rectangle in the strip, at most 8 points can exist. Why? Each half of that rectangle is a δ × δ square. Any two points in the same half are ≥ δ apart (we already found the best in each half). You can fit at most 4 points in a δ × δ square under that constraint. Two squares → at most 8 points total.

So for each point in the strip, you only need to compare it against the next 7 points in y-order. That makes the strip scan \(O(n)\) — not \(O(n^2)\)!

Getting to \(O(n \log n)\)

If you sort the strip by y at each recursive level, the combine step costs \(O(n \log n)\), giving T(n) = 2T(n/2) + \(O(n \log n)\) → \(O(n \log^2 n)\). But pre-sort all points by y once before recursing (just like merge sort maintains a sorted list during merging), and the strip scan becomes \(O(n)\). Now T(n) = 2T(n/2) + \(O(n)\) → \(O(n \log n)\). Same trick as merge sort!

Note: The strip can only have 8 points in any δ × 2δ box — that's the packing argument. It turns what looks like an \(O(n^2)\) strip scan into \(O(n)\). The geometry does the heavy lifting.

Closest Pair — Divide & Conquer

import math


def dist(p, q):
    return math.hypot(p[0]-q[0], p[1]-q[1])


def strip_closest(strip, d):
    best = d
    strip.sort(key=lambda p: p[1])
    for i in range(len(strip)):
        j = i + 1
        while j < len(strip) and strip[j][1] - strip[i][1] < best:
            best = min(best, dist(strip[i], strip[j]))
            j += 1
    return best


def closest(pts):
    pts.sort()
    def rec(P):
        if len(P) <= 3:
            best = float('inf')
            for i in range(len(P)):
                for j in range(i+1, len(P)):
                    best = min(best, dist(P[i], P[j]))
            return best
        mid = len(P) // 2
        midX = P[mid][0]
        d = min(rec(P[:mid]), rec(P[mid:]))
        strip = [p for p in P if abs(p[0] - midX) < d]
        return min(d, strip_closest(strip, d))
    return rec(pts)


points = [(2,3),(5,1),(1,6),(8,9),(3,7),(4,2)]
print(f"{closest(points):.4f}")  # 2.2361
Output
2.2361

Complexity

🐢 Naive all-pairs checkEvery pair of n points checked — unusable for large n
Quadratic\(O(n^2)\)
📐 D&C without pre-sortRe-sorting the strip by y at each level adds an extra log factor
Near-linearithmic\(O(n \log^2 n)\)
🚀 D&C with pre-sorted y listMaintain global y-order across recursive calls; strip scan is \(O(n)\)
Linearithmic\(O(n \log n)\)
📦 SpaceScratch arrays for sorted lists and strip candidates
Linear auxiliary\(O(n)\)
🔎 Strip scan per pointPacking argument: δ × 2δ box holds ≤ 8 points
Constant\(O(1)\) — at most 7 neighbors

Quick check

Why do we only check points within δ of the dividing line in the strip?

Continue reading

D&C Pattern
Split the problem, solve the pieces, combine the results
→
Merge Sort
Split, sort each half, merge — guaranteed \(O(n \log n)\) every time
→
Recurrence Relations
A recipe that calls itself — until it's simple enough to solve
→