Closest Pair of Points

Finds the two closest points in a 2D plane in O(n log n) time.

Step 1 of 26

Closest Pair of Points: 11 points. Sort by x, then divide and conquer. We recursively find the closest pair in left/right halves, then check the strip near the dividing line.

▶Algorithm

ClosestPair(P):
sort P by x-coordinate
if |P| ≤ 3: brute-force all pairs
  compare each pair, track minimum
mid = median x; divide into left, right
δ_L = ClosestPair(left)
δ_R = ClosestPair(right)
δ = min(δ_L, δ_R)
check strip within ±δ of mid
return min(δ, strip minimum)

Legend

Comparing

Best pair

Strip (±δ)

Divide by median x. Recurse on each half. Then check points within ±δ of the divide line (at most 8 per point). O(n log n) total.

1 / 26Speed