Home | | Design and Analysis of Algorithms | The Closest Pair Problem by Divide and Conquer

# The Closest Pair Problem by Divide and Conquer

In this section, we discuss more sophisticated and asymptotically more efficient algorithms for these problems, which are based on the divide-and-conquer technique.

The Closest-Pair and Convex-Hull Problems by Divide-and-Conquer

In previews Section , we discussed the brute-force approach to solving two classic prob-lems of computational geometry: the closest-pair problem and the convex-hull problem. We saw that the two-dimensional versions of these problems can be solved by brute-force algorithms in  (n2) and O(n3) time, respectively. In this section, we discuss more sophisticated and asymptotically more efficient algorithms for these problems, which are based on the divide-and-conquer technique.

The Closest-Pair Problem

Let P be a set of n > 1 points in the Cartesian plane. For the sake of simplicity, we assume that the points are distinct. We can also assume that the points are ordered in nondecreasing order of their x coordinate. (If they were not, we could sort them first by an efficeint sorting algorithm such as mergesort.) It will also be convenient to have the points sorted in a separate list in nondecreasing order of the y coordinate; we will denote such a list Q.

If 2 Ōēż n Ōēż 3, the problem can be solved by the obvious brute-force algorithm. If n > 3, we can divide the points into two subsets Pl and Pr of n/2 and n/2 points, respectively, by drawing a vertical line through the median m of their x coordinates so that n/2 points lie to the left of or on the line itself, and n/2 points lie to the right of or on the line. Then we can solve the closest-pair problem recursively for subsets Pl and Pr . Let dl and dr be the smallest distances between pairs of points in Pl and Pr , respectively, and let d = min{dl, dr }.

Note that d is not necessarily the smallest distance between all the point pairs because points of a closer pair can lie on the opposite sides of the separating line. Therefore, as a step combining the solutions to the smaller subproblems, we need to examine such points. Obviously, we can limit our attention to the points inside the symmetric vertical strip of width 2d around the separating line, since the distance between any other pair of points is at least d (Figure 5.7a).

Let S be the list of points inside the strip of width 2d around the separating line, obtained from Q and hence ordered in nondecreasing order of their y coor-dinate. We will scan this list, updating the information about dmin, the minimum distance seen so far, if we encounter a closer pair of points. Initially, dmin = d, and

subsequently dmin Ōēż d. Let p(x, y) be a point on this list. For a point p (x , y ) to have a chance to be closer to p than dmin, the point must follow p on list S and the difference between their y coordinates must be less than dmin (why?). Geometri-

cally, this means that p must belong to the rectangle shown in Figure 5.7b. The principal insight exploited by the algorithm is the observation that the rectangle can contain just a few such points, because the points in each half (left and right) of the rectangle must be at least distance d apart. It is easy to prove that the total number of such points in the rectangle, including p, does not exceed eight (Prob-lem 2 in this sectionŌĆÖs exercises); a more careful analysis reduces this number to six (see [Joh04, p. 695]). Thus, the algorithm can consider no more than five next points following p on the list S, before moving up to the next point.

Here is pseudocode of the algorithm. We follow the advice given in Section 3.3 to avoid computing square roots inside the innermost loop of the algorithm.

ALGORITHM                 EfficientClosestPair(P , Q)

//Solves the closest-pair problem by divide-and-conquer

//Input: An array P of n Ōēź 2 points in the Cartesian plane sorted in

nondecreasing order of their x coordinates and an array Q of the

same points sorted in nondecreasing order of the y coordinates //Output: Euclidean distance between the closest pair of points

if n Ōēż 3

return the minimal distance found by the brute-force algorithm

else

copy the first n/2 points of P to array Pl copy the same n/2 points from Q to array Ql copy the remaining n/2 points of P to array Pr copy the same n/2 points from Q to array Qr dl ŌåÉ EfficientClosestPair(Pl, Ql)

dr ŌåÉ EfficientClosestPair(Pr , Qr )

d ŌåÉmin{dl, dr }

m ŌåÉ P [ n/2  ŌłÆ 1].x

copy all the points of Q for which |x ŌłÆ m| < d into array S[0..num ŌłÆ 1] dminsq ŌåÉ d2

for i ŌåÉ 0 to num ŌłÆ 2 do k ŌåÉ i + 1

while k Ōēż num ŌłÆ 1 and (S[k].y ŌłÆ S[i].y)2 < dminsq

dminsq ŌåÉ min((S[k].x ŌłÆ S[i].x)2+ (S[k].y ŌłÆ S[i].y)2, dminsq) k ŌåÉ k + 1

return sqrt(dminsq)

The algorithm spends linear time both for dividing the problem into two problems half the size and combining the obtained solutions. Therefore, assuming as usual that n is a power of 2, we have the following recurrence for the running time of the algorithm:

T (n) = 2T (n/2) + f (n),

where f (n) Ōłł  (n). Applying the Master Theorem (with a = 2, b = 2, and d = 1), we get T (n) Ōłł  (n log n). The necessity to presort input points does not change the overall efficiency class if sorting is done by a O(n log n) algorithm such as mergesort. In fact, this is the best efficiency class one can achieve, because it has been proved that any algorithm for this problem must be in  (n log n) under some natural assumptions about operations an algorithm can perform (see [Pre85, p. 188]).

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Introduction to the Design and Analysis of Algorithms : Divide and Conquer : The Closest Pair Problem by Divide and Conquer |