Closest Pair
Find the nearest pair of points in O(n log n) with divide and conquer and a y-sorted strip check.
Closest Pair
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Closest pair is the standard reminder that geometry problems often become about ordering, not formulas. The naive \(O(n^2)\) scan compares every pair of points. The divide-and-conquer solution wins by proving that after solving left and right halves, only a tiny number of cross-half candidates still matter.
When to Use It
Use it when:
the task asks for the nearest pair under Euclidean distance,
the points are static,
\(n^2\) comparisons are too expensive.
Core Idea
Sort points by \(x\), split at the middle, solve both halves recursively, and let \(d\) be the better of the two distances. Any cross-half answer must lie in the vertical strip of width \(2d\) around the split line.
Key Insight
After sorting the strip by \(y\), each point only needs to be checked against a constant number of later points. The packing argument is the heart of the algorithm: too many points inside a small \(d \times 2d\) neighborhood would force two of them to be closer than \(d\) already.
Worked Problem
Problem.
Given \(n\) watchtowers on a plane, find the squared distance between the two closest towers.
Algorithm outline.
Sort once by \(x\).
Recurse on left and right halves.
Merge the halves by \(y\).
Build the strip and check only the next few points in \(y\)-order.
Correctness Intuition
The recursive answers handle pairs entirely inside one half. For cross-half pairs, both points must be within distance \(d\) of the dividing line; otherwise their \(x\)-difference alone is already too large. Inside the strip, the packing bound limits how many candidates each point can have.
Complexity Analysis
With the standard merge-by-\(y\) implementation, the recurrence is \[ T(n) = 2T(n/2) + O(n), \] so the total complexity is \(O(n \log n)\).
Implementation
The code keeps points sorted by \(x\), performs the recursive divide-and-conquer, and returns the minimum squared distance as a 64-bit integer.
Common Pitfalls
Re-sorting the strip from scratch at every recursion level and losing the \(O(n \log n)\) bound.
Using floating point even though squared integer distances are enough.
Forgetting duplicates; the answer can be \(0\).
Mixing up the strip width when working with squared distances.
Variants / Extensions
Manhattan-metric variants after coordinate transforms.
Dynamic closest pair, which is a much harder data-structure problem.
Closest pair in higher dimensions with more expensive constants.
Practice Problems
Static Euclidean closest pair.
Detect duplicates or near-collisions in large point sets.
Any geometry divide-and-conquer where only a strip of cross-boundary candidates survives.
References
Code
Contest-ready reference implementation for the idea explained above.
struct Point {
long long x;
long long y;
};
long long dist2(const Point& a, const Point& b) {
long long dx = a.x - b.x;
long long dy = a.y - b.y;
return dx * dx + dy * dy;
}
long long closest_pair_rec(vector<Point>& points, vector<Point>& buffer, int left, int right) {
if (right - left <= 3) {
long long best = numeric_limits<long long>::max();
for (int i = left; i < right; ++i) {
for (int j = i + 1; j < right; ++j) {
best = min(best, dist2(points[i], points[j]));
}
}
sort(points.begin() + left, points.begin() + right, [](const Point& a, const Point& b) {
return a.y < b.y;
});
return best;
}
int mid = (left + right) / 2;
long long mid_x = points[mid].x;
long long best = min(
closest_pair_rec(points, buffer, left, mid),
closest_pair_rec(points, buffer, mid, right)
);
merge(
points.begin() + left, points.begin() + mid,
points.begin() + mid, points.begin() + right,
buffer.begin(),
[](const Point& a, const Point& b) { return a.y < b.y; }
);
copy(buffer.begin(), buffer.begin() + (right - left), points.begin() + left);
vector<Point> strip;
for (int i = left; i < right; ++i) {
long long dx = points[i].x - mid_x;
if (dx * dx < best) {
for (int j = (int)strip.size() - 1; j >= 0; --j) {
long long dy = points[i].y - strip[j].y;
if (dy * dy >= best) break;
best = min(best, dist2(points[i], strip[j]));
}
strip.push_back(points[i]);
}
}
return best;
}
long long closest_pair_squared(vector<Point> points) {
sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
});
vector<Point> buffer(points.size());
return closest_pair_rec(points, buffer, 0, (int)points.size());
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.