Closest Pair of Points

Problem: Given $n$ points in 2D, find the closest pair.

Brute force: Check all pairs. $O(n^2)$.

D&C approach: $1.$ Sort points by $x$-coordinate.

$2.$ Divide: Split into left and right halves by $x$.

$3.$ Conquer: Recursively find closest pair in each half.

$4.$ Combine: Check pairs crossing the dividing line within a strip of width $2d$ (where $d$ is the min from both halves).

The strip check: Sort strip points by $y$. For each point, only check the next $7$ points (geometry limits candidates).

Time: $O(n \log^2 n)$ with careful implementation (can be $O(n \log n)$ with optimization).