# Finding The Closest Pair Of Points

We next show that at most 8 points of *P* can reside within this *δ* × 2*δ* rectangle. Consider the *δ* × *δ* square forming the left half of this rectangle. Since all points within *P _{L}* are at least

*δ*units apart, at most 4 points can reside within this square; Figure 33.11(b) shows how. Similarly, at most 4 points in

*P*can reside within the

_{R}*δ*×

*δ*square forming the right half of the rectangle. Thus, at most 8 points of

*P*can reside within the

*δ*× 2

*δ*rectangle. (Note that since points on line

*l*may be in either

*P*or

_{L}*P*, there may be up to 4 points on

_{R}*l*. This limit is achieved if there are two pairs of coincident points such that each pair consists of one point from

*P*and one point from

_{L}*P*, one pair is at the intersection of

_{R}*l*and the top of the rectangle, and the other pair is where

*l*intersects the bottom of the rectangle.)

Having shown that at most 8 points of *P* can reside within the rectangle, it is easy to see that we need only check the 7 points following each point in the array *Y*′.Still assuming that the closest pair is *p _{L}* and

*p*, let us assume without loss of generality that

_{R}*p*precedes

_{L}*p*in array

_{R}*Y*′. Then, even if

*p*occurs as early as possible in

_{L}*Y*′ and

*p*occurs as late as possible,

_{R}*p*is in one of the 7 positions following

_{R}*p*. Thus, we have shown the correctness of the closest-pair algorithm.

_{L}
**Implementation and running time**: As we have noted, our goal is to have the recurrence for the running time be *T*(*n*) = 2*T*(*n*/2) *O*(*n*), where *T*(*n*) is the running time for a set of *n* points. The main difficulty is in ensuring that the arrays *X _{L}, X_{R}, Y_{L}*, and

*Y*, which are passed to recursive calls, are sorted by the proper coordinate and also that the array

_{R}*Y*′ is sorted by

*y*-coordinate. (Note that if the array

*X*that is received by a recursive call is already sorted, then the division of set

*P*into

*P*and

_{L}*P*is easily accomplished in linear time.)

_{R}
The key observation is that in each call, we wish to form a sorted subset of a sorted array. For example, a particular invocation is given the subset *P* and the array *Y* , sorted by *y*-coordinate. Having partitioned *P* into *P _{L}* and

*P*, it needs to form the arrays

_{R}*Y*and

_{L}*Y*, which are sorted by

_{R}*y*-coordinate. Moreover, these arrays must be formed in linear time. The method can be viewed as the opposite of the MERGE procedure from merge sort in The divide-and-conquer approach: we are splitting a sorted array into two sorted arrays. The following pseudocode gives the idea.

1length[Y] ←_{L}length[Y] ← 0 2_{R}fori← 1tolength[Y] 3do ifY[i] ∈P4_{L}thenlength[Y] ←_{L}length[Y] 1 5_{L}Y[_{L}length[Y]] ←_{L}Y[i] 6elselength[Y] ←_{R}length[Y] 1 7_{R}Y[_{R}length[Y]] ←_{R}Y[i]

We simply examine the points in array *Y* in order. If a point *Y*[*i*] is in *P _{L}*, we append it to the end of array

*Y*; otherwise, we append it to the end of array

_{L}*Y*. Similar pseudocode works for forming arrays

_{R}*X*, and

_{L}, X_{R}*Y*′.

The only remaining question is how to get the points sorted in the first place. We do this by simply ** presorting** them; that is, we sort them once and for all

*before*the first recursive call. These sorted arrays are passed into the first recursive call, and from there they are whittled down through the recursive calls as necessary. The presorting adds an additional

*O*(

*n*lg

*n*) to the running time, but now each step of the recursion takes linear time exclusive of the recursive calls. Thus, if we let

*T*(

*n*) be the running time of each recursive step and

*T*′(

*n*) be the running time of the entire algorithm, we get

*T*′(

*n*) =

*T*(

*n*)

*O*(

*n*lg

*n*) and

Thus, *T*(*n*) = *O*(*n* lg *n*) and *T*′(*n*) = *O*(*n* lg *n*).