Closest Pair of Points

Find the two closest of $n$ points. Naive is $O(n^2)$; three better methods exist.

Method 1: sweep line with a set — the one to write

$O(n\log n)$, about 20 lines, and it reuses std::set.

long long closestPair(vector<P> p) {
    sort(p.begin(), p.end());                          // by x, then y
    set<pair<long long,long long>> box;                // active points, keyed by (y, x)
    long long best = LLONG_MAX;
    int left = 0;
    for (int i = 0; i < (int)p.size(); i++) {
        long long d = (long long)ceil(sqrt((long double)best));
        while (left < i && p[i].x - p[left].x > d) {   // drop points too far left
            box.erase({p[left].y, p[left].x});
            left++;
        }
        auto lo = box.lower_bound({p[i].y - d, LLONG_MIN});
        auto hi = box.upper_bound({p[i].y + d, LLONG_MAX});
        for (auto it = lo; it != hi; ++it)
            best = min(best, norm2(P{(long long)it->second, (long long)it->first} - p[i]));
        box.insert({p[i].y, p[i].x});
    }
    return best;                                        // SQUARED distance
}

Why it is $O(n\log n)$: the active set is a vertical strip of width $d$, and within any $d\times 2d$ window at most 6 points can be pairwise at distance $\ge d$. So each point examines $O(1)$ neighbours.

Returning the squared distance keeps everything exact.

Method 2: divide and conquer

Split at the median $x$, recurse, then check the strip of width $2d$ around the split line, sorted by $y$. The seven-point lemma bounds the strip scan at $O(n)$:

$T(n)=2T(n/2)+O(n)=O(n\log n).$

Merge the $y$-orders during the recursion rather than re-sorting. See Bentley-Shamos.

Method 3: randomised incremental — expected $O(n)$

1. Shuffle the points.
2. Maintain the best distance $d$ and a hash grid with cell size $d$.
3. Insert points one at a time, checking only the 9 neighbouring cells.
4. When $d$ shrinks, rebuild the grid.

long long closestRandomized(vector<P> p) {
    shuffle(p.begin(), p.end(), rng);
    long long best = norm2(p[1] - p[0]);
    unordered_map<long long, vector<int>> grid;
    long long cell = max(1LL, (long long)sqrt((long double)best));
    auto key = [&](long long x, long long y) { return x * 1000003LL + y; };
    auto rebuild = [&](int upto) {
        grid.clear();
        cell = max(1LL, (long long)sqrt((long double)best));
        for (int i = 0; i < upto; i++) grid[key(p[i].x / cell, p[i].y / cell)].push_back(i);
    };
    rebuild(2);
    for (int i = 2; i < (int)p.size(); i++) {
        long long gx = p[i].x / cell, gy = p[i].y / cell;
        bool shrunk = false;
        for (long long dx = -1; dx <= 1; dx++)
            for (long long dy = -1; dy <= 1; dy++)
                for (int j : grid[key(gx+dx, gy+dy)]) {
                    long long dd = norm2(p[i] - p[j]);
                    if (dd < best) { best = dd; shrunk = true; }
                }
        if (shrunk) rebuild(i + 1);
        else grid[key(gx, gy)].push_back(i);
    }
    return best;
}

The expected total rebuild cost is $O(n)$ — the $i$-th point improves the minimum with probability $O(1/i)$, and a rebuild costs $O(i)$, so the sum telescopes.

Comparison

Method	Time	Code	Notes
Brute force	$O(n^2)$	3 lines	fine to $n\approx 5000$
Sweep + set	$O(n\log n)$	~20 lines	the default
Divide and conquer	$O(n\log n)$	~40 lines	classic; also gives all near pairs
Randomised + grid	$O(n)$ expected	~40 lines	fastest, needs a good hash
KD-tree	$O(n\log n)$ expected	~60 lines	reusable for other queries
Delaunay	$O(n\log n)$	very long	the closest pair is a Delaunay edge

Variants

Variant	Approach
Farthest pair	it is a hull diameter — rotating calipers
Closest pair in 3D	the same sweep with a 2D active structure, $O(n{\log }^{2}n)$
Closest pair under $L_1$ / $L_{\infty }$	rotate 45° (Manhattan) or sweep directly
Closest pair with insertions	the randomised grid handles it naturally
All pairs within distance $d$	grid buckets of side $d$, then check 9 cells
$k$ closest pairs	a heap over the candidates found by the sweep
Closest pair between two sets	the same sweep, ignoring same-set pairs

The bucket trick

When the coordinate range is bounded and the answer is expected to be small, a plain grid of side $d$ answers “all pairs within $d$” in $O(n+\text{output})$. It is the workhorse for collision detection and $n$-body simulation, and often simpler than any of the above.

See also: Bentley-Shamos · Sweep Line · KD-Tree