Click or tap the board to add a point (drag to orbit). Orange blade = current dividing line, violet slab = strip of half-width δ.
Given n points, find the pair with the smallest Euclidean distance d(p,q)=sqrt((px-qx)^2+(py-qy)^2). Brute force tests all n(n-1)/2 pairs: O(n^2).
Divide and conquer (Shamos and Hoey, 1975): sort by x, split at the median, solve both halves to get δ=min(δL,δR). A closer pair that straddles the line must lie inside the strip |x-xm|<δ. Sorted by y, each strip point needs comparing only with followers closer than δ in y; a packing argument (at most 6 or 7 points fit in a δ by 2δ box when each half has spacing at least δ) bounds that to a constant. Recurrence T(n)=2T(n/2)+O(n) gives O(n log n) comparisons (this page re-sorts the strip in each call, so wall time is O(n log^2 n) unless the merge-sort variant is used).
A grid with cell size equal to an upper bound on d also solves it in expected O(n); it is used here only as an independent cross-check.
Simplifications: exact points in the plane, floating point doubles, strict inequality in the strip so ties are handled; the 3D board is only a drawing of the plane (y of the algorithm maps to depth). Distance evaluations are counted, not clock time.