5.4 Finding the Closest Pair of Points

Given n points in the plane,find the pair that is closest together. The brute-force attempt at solving this problem would cost us O(n²) time. Our goal is to find an efficient algorithm that runs in O(nlogn) time.

Let P = {p₁,p₂,…,p_n} where p_i has coordinates(x_i,y_i). For two points, p_i,p_j in P,d(p_i,p_j) = the Standard Euclidean distance between them.
Our Goal: Find a pair of points (p_i,p_j) that minimizes d(p_i,p_j).
Our plan: apply the divide and conquer style used in Mergesort by finding the closest pair among the points in the left half of P and the closest pair among the points on the right half of P, we then get the overall solution in O(n) time. With this plan, we can get an O(nlogn) running time.

Closest-Pair(p1, …, pn)

Compute separation line L such that half the points

are on one side and half on the other side.

δ1 = Closest-Pair(left half)

δ2 = Closest-Pair(right half)

δ = min(δ1, δ2)

Delete all points further than δ from separation line L

Sort remaining points by y-coordinate.

Scan points in y-order and compare distance between each point and next 7 neighbors.

If any of these distances is less than δ, update δ.

return δ

The running time of this algorithm is O(nlogn).
I give this section 8/10