Bentley-Shamos Algorithm

Purpose: The divide and conquer approach to the closest pair of points, in $O(n\log n)$ — and the model for a whole family of “divide the plane, recurse, merge with a strip” geometric algorithms.

Closest pair by divide and conquer

1. Sort the points by $x$ once, up front.
2. Split at the median $x$ into left half $L$ and right half $R$.
3. Recurse: let $d=\min (d_L,d_R)$.
4. The strip. Any closer pair must straddle the split line, so both points lie within distance $d$ of it. Collect those points, sorted by $y$.
5. The seven-point lemma. For each point in the strip, only the next at most 7 points in $y$-order can be within $d$ — because a $d\times 2d$ rectangle can hold at most 8 points that are pairwise $\ge d$ apart. So the strip scan is $O(n)$, not $O(n^2)$.

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

Keeping the $y$-order by merging during the recursion (rather than re-sorting) is what keeps the merge step linear.

Code

// pts sorted by x; ys is a scratch buffer. Returns squared distance.
long long closest(vector<Point>& px, vector<Point>& py) {
    int n = px.size();
    if (n <= 3) { /* brute force, and sort py */ return brute(px, py); }
 
    int mid = n / 2;
    long long midx = px[mid].x;
    vector<Point> lx(px.begin(), px.begin() + mid), rx(px.begin() + mid, px.end());
    vector<Point> ly, ry;
    long long d = min(closest(lx, ly), closest(rx, ry));
 
    py.clear();
    merge(ly.begin(), ly.end(), ry.begin(), ry.end(), back_inserter(py), byY);
 
    vector<Point> strip;
    for (auto& p : py) if (sq(p.x - midx) < d) strip.push_back(p);
    for (size_t i = 0; i < strip.size(); i++)
        for (size_t j = i + 1; j < strip.size() && sq(strip[j].y - strip[i].y) < d; j++)
            d = min(d, dist2(strip[i], strip[j]));
    return d;
}

Complexity

• Time: $O(n\log n)$
• Space: $O(n)$

The faster practical alternative

A randomized incremental algorithm solves closest pair in expected $O(n)$: shuffle the points, maintain a hash grid with cell size equal to the current best distance $d$, insert points one at a time checking only the 9 neighbouring cells, and rebuild the grid whenever $d$ shrinks. About 40 lines, no recursion, and genuinely linear. See Closest Pair.

The Bentley-Shamos pattern

The same skeleton — split by a median line, recurse, merge across a narrow strip — solves many problems:

Problem	Merge step
Closest pair	strip of width $2d$, 7-point lemma
All nearest neighbours	strip plus per-point candidate lists
Maximal points / Pareto frontier	merge the two staircases
Dominance counting	count left points dominating right points during merge
Smallest enclosing circle (Shamos)	superseded by Welzl
CDQ divide and conquer	left half’s updates applied to right half’s queries

That last row is the important one for competitive programming: CDQ divide and conquer is exactly this pattern applied to offline queries with several dimensions, and it is the standard tool for 3D partial-order counting problems.

Variants / Use Cases

• Closest Pair of Points — the topic page
• CDQ Divide and Conquer — the contest-relevant descendant
• KD-Tree — the structure for repeated nearest-neighbour queries
• Sweep line — the other general geometric technique