Closest pair of points

Points0
Distance evaluations0
Brute force would need0
Best distance so far-
Strip width 2δ-

Click or tap the board to add a point (drag to orbit). Orange blade = current dividing line, violet slab = strip of half-width δ.

The science

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.

Numerical self-checks (running)
    Drag: rotate · Wheel / pinch: zoom
    Made with ๐ŸŸ  Blender ยท Three.js