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

S 1 S 2

stripL stripR stripL stripR

stripL stripR

d 1

d 2

d

p

p

mid

q [ r ]

d d

d d

(a) (b) (c)

F IGURE 22.5

The midpoint divides the points into two sets of equal size.

L ISTING 22.9

Algorithm for Obtaining stripL and stripR
1 for each point p in pointsOrderedOnY
2 if (p is in S1 and mid.x - p.x <= d)
3 append p to stripL;
4 else if (p is in S2 and p.x - mid.x <= d)
5 append p to stripR;

stripL

stripR

Let the points in stripL and stripR be { p 0 , p 1 , c , p k } and { q 0 , q 1 , c , q t }, as shown in
Figure 22.5c. The closest pair between a point in stripL and a point in stripR can be found
using the algorithm described in Listing 22.10.

L ISTING 22.10

Algorithm for Finding the Closest Pair
in Step 3
1 d = min(d1, d2);
2 r = 0 ; // r is the index of a point in stripR
3 for (each point p in stripL) {
4 // Skip the points in stripR below p.y - d
5 while (r < stripR.length && q[r].y <= p.y - d)
6 r++;
7
8 let r1 = r;
9 while (r1 < stripR.length && |q[r1].y - p.y| <= d) {
10 // Check if (p, q[r1]) is a possible closest pair
11 if (distance(p, q[r1]) < d) {
12 d = distance(p, q[r1]);
13 (p, q[r1]) is now the current closest pair;
14 }
15
16 r1 = r1 + 1 ;
17 }
18 }

update closest pair

The points in stripL are considered from p 0 , p 1 , c , p k in this order. For a point p in
stripL , skip the points in stripR that are below p.y - d (lines 5-6). Once a point is
skipped, it will no longer be considered. The while loop (lines 9-17) checks whether (p,
q[r1]) is a possible closest pair. There are at most six such q[r1] pairs, because the distance
between two points in stripR cannot be less than d . So the complexity for finding the closest
pair in Step 3 is O ( n ).