2 Closest Pair: The One Dimensional Case

2.1 Introduction

In order to present faster algorithms for solving the closest pair problem than the brute force approach, we will begin by attacking the problem in ont dimension and then attempting to generalize to the plane.

[Top] [Bottom] [Home]

2.2 Closest Pair on the Line

Consider a set of points S on a line (see figure 2.1), our goal is to determine which two of these points are minimally distant from eachother.

We can partition this set into two sets by some point m. We'll call these sets S1 and S2 such that the points in the first set are to the left of m and those in the second set are to the right.
Assume that {p1,p2} are the points defining the closest pair in S1, and that {q1,q2} are the points defining the closest pair in S2 (these solutions were calculated using our recursive solution to the smaller sub-problem).

Finally, let d be the smaller of these two solutions. We can now say that the closest pair in all of S is one of:
  1. {p1,p2}
  2. {q1,q2}
  3. some pair {p3,q3} that has one point in each of S1 and S2.
    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 S1 and S2, 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 S1 and S2.

    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 S1 and S2. 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 {p3,q3} 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(nlogn) 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