Page 554 - Discrete Mathematics and Its Applications

8.3 Divide-and-Conquer Algorithms and Recurrence Relations 533

In this illustration the problem of finding the
closest pair in a set of 16 points is reduced to
d L
d R two problems of finding the closest pair in
a set of eight points and the problem of
closest determining whether there are points closer
pair than d = min(d , d ) within the strip of
L
R
width 2d centered at .
L R

d d
FIGURE 1 The Recursive Step of the Algorithm for Solving the Closest-Pair Problem.

Solution: To solve this problem we can first determine the distance between every pair of
2
points and then find the smallest of these distances. However, this approach requires O(n )
It took researchers more
than 10 year to find an computations of distances and comparisons because there are C(n, 2) = n(n − 1)/2 pairs of
algorithm with O(n log n) points. Surprisingly, there is an elegant divide-and-conquer algorithm that can solve the closest-
complexity that locates pair problem for n points using O(n log n) computations of distances and comparisons. The
the closest pair of points algorithm we describe here is due to Michael Samos (see [PrSa85]).
among n points. k
For simplicity, we assume that n = 2 , where k is a positive integer. (We avoid some
technical considerations that are needed when n is not a power of 2.) When n = 2, we have only
one pair of points; the distance between these two points is the minimum distance. At the start
of the algorithm we use the merge sort twice, once to sort the points in order of increasing x
coordinates, and once to sort the points in order of increasing y coordinates. Each of these sorts
requires O(n log n) operations. We will use these sorted lists in each recursive step.
Therecursivepartofthealgorithmdividestheproblemintotwosubproblems,eachinvolving
half as many points. Using the sorted list of the points by their x coordinates, we construct a
vertical line dividing the n points into two parts, a left part and a right part of equal size, each
containing n/2 points, as shown in Figure 1. (If any points fall on the dividing line , we divide
them among the two parts if necessary.) At subsequent steps of the recursion we need not sort
on x coordinates again, because we can select the corresponding sorted subset of all the points.
This selection is a task that can be done with O(n) comparisons.
There are three possibilities concerning the positions of the closest points: (1) they are both
in the left region L, (2) they are both in the right region R, or (3) one point is in the left region
and the other is in the right region. Apply the algorithm recursively to compute d L and d R ,
where d L is the minimum distance between points in the left region and d R is the minimum
distance between points in the right region. Let d = min(d L ,d R ). To successfully divide the
problem of finding the closest two points in the original set into the two problems of finding the
shortest distances between points in the two regions separately, we have to handle the conquer
part of the algorithm, which requires that we consider the case where the closest points lie in
different regions, that is, one point is in L and the other in R. Because there is a pair of points
at distance d where both points lie in R or both points lie in L, for the closest points to lie in
different regions requires that they must be a distance less than d apart.
For a point in the left region and a point in the right region to lie at a distance less than d apart,
these points must lie in the vertical strip of width 2d that has the line as its center. (Otherwise,
the distance between these points is greater than the difference in their x coordinates, which
exceeds d.) To examine the points within this strip, we sort the points so that they are listed in
order of increasing y coordinates, using the sorted list of the points by their y coordinates. At