MathMathematical Algorithms

Closest Pair of Points

Find the two closest points among n points in the plane in O(n log n) by splitting on x, recursing, and checking only a thin strip around the split line.

Learn Closest Pair of Points →

Points — Comma separated "x y" pairs, 4 to 12 points, coordinates 0-420 — e.g. "40 60, 130 200, 260 90"

recursion stack (depth)

(top level)

best so far

pair	distance	note
—	∞

1/4010 points, sorted left to right by x. Checking every pair is O(n²) — 45 comparisons here — and the point of divide and conquer is to get the same answer while looking at only a linear number of pairs per level of the recursion.

Left half of the splitRight half of the splitIn the strip around the dividing linePair being comparedClosest pair found so farOutside the current subproblem

PseudocodeLearn Closest Pair of Points →

1sort points by x
2rec(lo, hi):
3  if hi - lo <= 3: return min distance over all pairs   # brute force, O(1)
4  mid = (lo + hi) / 2;  xm = P[mid].x
5  d = min(rec(lo, mid), rec(mid, hi))
6  strip = points with |x - xm| < d, in increasing y
7  for i in strip:
8    for j = i+1 while strip[j].y - strip[i].y < d:      # at most 7 such j
9      d = min(d, dist(strip[i], strip[j]))
10  return d

Variables

points10

allPairs45

Complexity

worst O(n log n)

space O(n)

Speed