[Top] [Bottom] [Home]

We can partition this set into two sets by some point

Assume that {

Finally, let

- {
*p*_{1},*p*_{2}} - {
*q*_{1},*q*_{2}} - some pair {
*p*_{3},*q*_{3}} that has one point in each of*S*_{1}and*S*_{2}.**Figure 2.1:**Divide-and-conquer in one dimension.

The question now is "which one"?

KEY OBSERVATION: Notice that if the closest pair has one point contributed from each subset*S*_{1}and*S*_{2}, then*both*of these points must be within*d*of the midpoint*m*.

WHY IS THIS? If one of these points was further from the midpoint, then it couldn't possibly be closer than*d*units to a point in the other subset, and hence couldn't possibly define a pair closer than*d*, which has already been established as the minimum of the two sub-solutions computed for*S*_{1}and*S*_{2}.

We make one final observation to clinch an efficient algorithm: since the minimum distance among the sub-solutions was*d*, there can be only a maximum of*one*point within*d*of*m*in each subset*S*_{1}and*S*_{2}. Otherwise, the two points within that interval would define a pair within one of the subsets closer than*d*, which contradicts the minimality of*d*.

Hence in order to see which of our three options is the correct closest pair, we only need to test one pair of points to see if there is a pair {*p*_{3},*q*_{3}} that defines a pair closer than*d*! Hence the merging of our solutions is certainly done in linear time, so we have indeed described an O(*n*log*n*) algorithm.

This may all seem a little redundant to do in 1-Dimension. After all couldn't we just sweep across the line testing adjacent points? Yes we could, and in fact in the following two sections, we will be looking at generalizations of both of these methods.

[Top] [Bottom] [Home]

Sam Bakhtiar SANJABI Last modified: Tue Apr 11 23:50:47 EDT 2000