Closest Pair of Points

2D Spatial Visualization

Divide & Conquer at work

Step:1 / 82

Speed1x

Points16

State Tracker

Current Delta∞

Best PairNone

Lower delta means closer points found.

Current Step

split phase

Splitting points set at median x into left and right subsets.

Optimized Pseudocode

Pseudocode

1function closestPair(points):
2  sort points by x
3  return recursive(points)
4function recursive(P):
5  if |P| <= 3: return bruteForce(P)
6  mid = |P|/2; L = P[0:mid]; R = P[mid:]
7  d = min(recursive(L), recursive(R))
8  strip = points within d of mid line
9  return min(d, stripClosest(strip, d))

What to notice?

Notice how the vertical midline moves as we recurse.
The cyan strip represents the region where a better pair could exist across the split.
Observe that in the strip, we only compare a point with its neighbors sorted by Y-coordinate.