DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 844

F IGURE 22.4

The closet-pair animation draws a line to connect the closest pair of points
dynamically as points are added and removed interactively.

We will use an approach called divide-and-conquer to solve this problem. The approach
divides the problem into subproblems, solves the subproblems, then combines the solutions of
the subproblems to obtain the solution for the entire problem. Unlike the dynamic program-
ming approach, the subproblems in the divide-and-conquer approach don't overlap. A sub-
problem is like the original problem with a smaller size, so you can apply recursion to solve
the problem. In fact, all the solutions for recursive problems follow the divide-and-conquer
approach.
Listing 22.8 describes how to solve the closest pair problem using the divide-and-conquer
approach.

divide-and-conquer

L ISTING 22.8

Algorithm for Finding the Closest Pair
Step 1: Sort the points in increasing order of x -coordinates. For the
points with the same x -coordinates, sort on y -coordinates. This results
in a sorted list S of points.
Step 2: Divide S into two subsets, S 1 and S 2 , of equal size using the
midpoint in the sorted list. Let the midpoint be in S 1 . Recursively find
the closest pair in S 1 and S 2 . Let d 1 and d 2 denote the distance of the
closest pairs in the two subsets, respectively.
Step 3: Find the closest pair between a point in S 1 and a point in S 2 and
denote their distance as d 3 . The closest pair is the one with the dis-
tance min( d 1 , d 2 , d 3 ).

Selection sort takes O ( n 2 ) time. In Chapter 23 we will introduce merge sort and heap sort.
These sorting algorithms take O ( n log n ) time. Step 1 can be done in O ( n log n ) time.
Step 3 can be done in O ( n ) time. Let d min( d 1 , d 2 ). We already know that the closest-

pair distance cannot be larger than d . For a point in S 1 and a point in S 2 to form the closest
pair in S , the left point must be in stripL and the right point in stripR , as illustrated in
Figure 22.5a.
For a point p in stripL , you need only consider a right point within the d

=

*

2 d rectangle,
as shown in 22.5b. Any right point outside the rectangle cannot form the closest pair with
p . Since the closest-pair distance in S 2 is greater than or equal to d , there can be at most six
points in the rectangle. Thus, for each point in stripL , at most six points in stripR need to
be considered.
For each point p in stripL , how do you locate the points in the corresponding d

2 d
rectangle area in stripR ? This can be done efficiently if the points in stripL and stripR
are sorted in increasing order of their y -coordinates. Let pointsOrderedOnY be the list of
the points sorted in increasing order of y -coordinates. pointsOrderedOnY can be obtained
beforehand in the algorithm. stripL and stripR can be obtained from pointsOrderedOnY
in Step 3 as shown in Listing 22.9.

*