Closest Pair of Points

Divide and conquer with a narrow cross-boundary strip

Improve on checking every pair

Comparing every pair of n planar points takes O(n^2) time. The divide-and-conquer algorithm first sorts points by x-coordinate, splits them at the median, and recursively finds the closest pair in each half.

The merge step must inspect the boundary

Let delta be the better distance from the two halves. A closer pair with one point on each side must lie inside a strip of width 2 * delta around the midline. Sort those strip points by y-coordinate; each point only needs comparisons with the next few points whose y-gap is smaller than the current best distance.

The player shows the midline, the active strip, each candidate segment, and the best pair. In this data set the final closest pair crosses the split, which demonstrates why the merge step cannot stop after solving the two halves.

Plot 8 points sorted by x; divide and conquer will improve on the O(n^2) pair scan.

1function closest(pts: Pt[]): number {          // pts sorted by x
if (pts.length <= 3) return brute(pts);
const mid = pts.length >> 1;
const midX = (pts[mid - 1].x + pts[mid].x) / 2;  // midline
const dl = closest(pts.slice(0, mid));           // recurse on the left half
const dr = closest(pts.slice(mid));              // recurse on the right half
let d = Math.min(dl, dr);                        // δ
const strip = pts.filter(p => Math.abs(p.x - midX) < d)
                 .sort((a, b) => a.y - b.y);     // sort the delta strip by y
for (let i = 0; i < strip.length; i++)
  for (let j = i + 1; j < strip.length &&
       strip[j].y - strip[i].y < d; j++)         // compare neighbors with y-gap < delta
    d = Math.min(d, dist(strip[i], strip[j]));   // a cross-strip pair may improve d
return d;
15}

Points8

Best distance-

1 / 10

Linear merge work per recursion level

A packing argument bounds the number of relevant y-neighbors by a constant. With points kept in y-order during merging, each recursion level costs O(n), giving T(n) = 2T(n/2) + O(n) = O(n log n) time and O(n) auxiliary space.

Merge invariant: before scanning the strip, the current best is already correct for all pairs that lie completely inside either half.

Compare this distance-based divide and conquer with the orientation tests in Convex Hull, or revisit ordered merging in Merge Sort.

Algorithm Visualizer

Closest Pair of Points

Improve on checking every pair

The merge step must inspect the boundary

Linear merge work per recursion level