Skip to content

Closest Pair of Points

Given \(n\) points in the plane, find the minimum Euclidean distance between two distinct points. Naive \(O(n^2)\) works for small \(n\); divide and conquer or a sweep line achieve \(O(n \log n)\).

Brute force

#include <vector>
#include <cmath>
#include <algorithm>
struct Point { double x, y; };

double dist2(const Point& a, const Point& b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}

double closestPairBrute(const std::vector<Point>& p) {
    int n = (int)p.size();
    double best = 1e300;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            best = std::min(best, dist2(p[i], p[j]));
    return std::sqrt(best);
}

Divide and conquer (sketch)

  1. Sort by \(x\). Split set by median \(x\); recursively solve left and right halves → \(\delta\) = min of two answers.
  2. Consider strip of points with \(|x - x_{\text{mid}}| < \delta\); sort strip by \(y\). For each point, only constant neighbors within \(\delta\) in \(y\) need checks (packing argument).

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

Plane sweep variant

Sweep a vertical line; maintain active set in a balanced structure ordered by \(y\); insert/delete points; for each new point query neighbors in \(y\) within distance window—often implemented with set + careful bounds.