The following is pseudo-code for the closesPair algorithm described above:

//A function that returns the distance between two points

Distance(p1, p2)

     return sqrt( (p1.x - p2.x)2 + (p2.y – p2.y)2)

 

//S is the set of points sorted by x
//p is the index of the first point in the subarray of S
//r is the index of the last point in the subarray of S

1.         ClosestPair(S, p, r)

2.              if p == r

3.                 return ∞

4.             if r - p == 1

5.                  return Distance(S[p], S[p+1])

6.             else

7.                   m = floor ((p+r)/2) //m is the index of the median (the x-coordinate is the vertical dividing line)

8.                   d1 = ClosestPair(S, p, m)

9.                   d2 = ClosestPair(S, m+1, r)

10.                 d = min(d1, d2)

11.                 SPrime = points in S within distance d from S[m].x sorted by y.

12.                 dPrime = BandClosestPair(Sprime, d)

13.                 return min( dPrime, d)

 

Answer the following questions:

 

What is the base case of the algorithm ClosestPair?

Does the pseudocode above handle the base case correctly? Why?

What line numbers in the algorithm above correspond to the divide step?

How long does the divide phase take? (Provide your answer in theta-notation)

Which lines correspond to the combine phase?

Assuming the merge step (11, 12) can be done in linear time (requires small changes to algorithm that you don’t need to worry about), write the recurrence for ClosestPair.

What is the running time of ClosestPair? (Provide answer in theta-notation).