Closest Pair of Points
In short: finding the two closest points among n by checking every pair
is O(n²). Divide and conquer brings it to O(n log n): sort by x, split in
half, find the closest pair in each half recursively, and keep the smaller
distance as best. The only question left is whether some pair straddles
the dividing line and beats best — and that can only happen within a
narrow strip of width 2 * best around the line. Sort that strip by y,
and for each point in it, only the next 7 points in y-order could
possibly be close enough to matter. That bound turns an O(n²) strip check
into O(n), so the whole algorithm is O(n log n): one sort, then a recursion
whose merge step is linear.
Two stops near the depot
Eight of Meridian's stops are scattered around a depot. Which two sit closest together?
(0,0) and (1,1) turn out to be the closest pair — a distance of
sqrt(2) ≈ 1.4142 — and the brute-force base case finds them directly,
because with 8 points the recursion's two halves (4 points each) both
bottom out at the n <= 3 base case almost immediately.
When the closest pair straddles the split
Split a batch of stops in half by x, and the closest pair isn't always inside one half — sometimes the real answer sits right across the dividing line, one point in each half:
(10, 10) is the last point in the left half, (11, 10) is the first
point in the right half — neither half's own brute-force search ever
compares them to each other, because they're never both on the same side of
the split. Each half thinks its best pair is 14+ apart, but the true
closest pair is right on the seam, a distance of exactly 1. Only the
strip step, which looks at points from BOTH halves near the dividing line,
can catch a pair like this.
Why the strip only needs 7 neighbours
It seems like the strip step should still cost O(n²) in the worst case —
until you notice that every point in the strip already has a neighbour no
closer than best (otherwise best would have been beaten already, by
one half or the other). That spacing guarantee means at most 8 strip points
can fit inside any delta x 2*delta box, so checking each point against the
next 7 in y-order is enough; anyone further down the sorted strip is
provably too far away in y alone to beat best.
best_d = 2 # squared distance, i.e. a real distance of sqrt(2)
delta = 2 ** 0.5
print(round(delta, 4))Quick practice
def dist2(a, b):
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
print(dist2((0, 0), (3, 4)) < dist2((0, 0), (1, 1)))points = [(0, 0), (1, 1), (2, 7), (3, 4), (5, 5), (6, 1), (8, 8), (9, 0)]
mid = len(points) // 2
print(points[mid])🎯 Your turn
Build closest_pair(points): return [pair, distance], the two closest
points and their real distance rounded to 4 decimal places.
closest_pair([(0,0), (6,1), (3,4), (9,0), (1,1), (8,8), (5,5), (2,7)])→[[(0,0), (1,1)], 1.4142]closest_pair([(0,0), (10,10)])→[[(0,0), (10,10)], 14.1421]
Hint: points arrives as plain [x, y] lists, so dedupe with
sorted({tuple(p) for p in points}), not sorted(set(points)) — a list
isn't hashable. Base case n <= 3: brute force. Else split at n // 2,
recurse on each half, keep the smaller squared distance, then check the
delta-wide strip around the split (sorted by y, each point against the
next 7) for anything closer still. Convert the winning pair's two points
back to lists before returning.
Press ▶ Run, try the Live App chips, then ✓ Check.