Chapter 5.4: Finding the Closest Pair of Points

Given n points on a plane, our goal is to find the pair that is closest together. Comparing every possible pairing would take O(n^2) time. However, it is possible to do this in O(nlogn) time.

We will denote the set of points by P={p_1,…, p_n}, where p_i has coordinates (x_i,y_i); and for two points p_i,p_j, d(p_i,p_j) to denote the Euclidean distance between them. We will also assume that all points have distinct coordinates. Our goal is to find a pair of coordinates p_i and p_j such that d(p_i,p_j) is minimized. We will approach this problem in a way that is similar to Mergesort: we will find the closest pair among the points in the left half of P and the closest pair among the right half of P.

Closest-Pair(P):

• construct P_x and P_y (sorted lists by x and y coordinate, respectively)
• (p_0*,p_1*) = Closest-Pair-Rec(P_x,P_y)

Closest-Pair-Rec(P_x,P_y):

• If |P|< = 3 then find closest pair by measuring all pairwise distances
• Construct Q_x,Q_y,R_x,R_y
• (q_0*,q_1*) = Closest-Pair-Rec(Q_x,Q_y)
• (r_0*,r_1*) = Closest-Pair-Rec(R_x,R_y)
• δ=min(d(q_0*,q_1*), d(r_0*,r_1*))
• x*=maximum x-coordinate of a point in set Q
• L={(x,y): x=x*}
• S= points in P within distance δ of L
• Construct S_y
• for each point s in S_y, compute distance from s to each of the next 15 points in S_y
• Let s,s' be pair achieving minimum of these distances
• If d(s,s')<δ then return (s,s')
• else if: if d(q_0*,q_1*) < d(r_0*,r_1*) then return (q_0*,q_1*)
• else: return (r_0*,r_1*)

this runs in O(nlogn)

I would rate this section a 6. The algorithm made more sense in class. I was really confused by all of the additional variables in this algorithm.