Closest Pair of Points

Why it matters

Closest pair is classic D&C. Understanding shapes geometric optimization.

The architecture

Sort by x.

Divide in half.

Recurse both.

Check strip near dividing line.

How it works end to end

Master theorem: T(n) = 2T(n/2) + O(n) = O(n log n).

Strip candidates: 7 per point in y-sorted order.

Alternative: KD-tree.