Algorithm
1. Sort by x. 2. Split in half. 3. Recurse. 4. δ = min of two halves. 5. Strip: points within δ of split line. Compare each to next 7 in y-sorted strip.
Advertisement
Why 7 neighbors suffice
Each point in strip has δ×2δ rectangle around it. Only 7 other points fit within this without violating δ.
Advertisement
Complexity
T(N) = 2T(N/2) + O(N) → O(N log N).
Randomized alternative
Rabin's O(N) expected: hash into grid of size δ, check nearby cells.