Search code examples
algorithmclosest

closest pair algorithm

I am trying to understand the closest pair algorithm. I understand about dividing the set in half. But I am having trouble understanding how to recursively compute the closest pair. I understand recursion, but do not understand how to compute the closest pair by recursion. If you have (1,2)(1,11)(7,8) how would recursion work on these?

Solution

  • If you mean this algorithm you do the following:

    1. Sort points: (1,2) (1,11) (7,8)
    2. Build two subsets: (1,2) (1,11) and (7,8)
    3. Run the algorithm on (1,2) (1,11) and on (7,8) separately <= this is where the recursion comes. The result is dLmin = 9 and dRmin = infinity (there is no second point on the right)
    4. dLRmin = sqrt(45)
    5. result = min(dLmin, dRmin, dLRmin) = sqrt(45)

    The recursion consists of the same steps as above. E.g. the call with (1,2) and (1,11) does:

    1. Sort points: (1,2) (1,11)
    2. Build two subsets: (1,2) and (1,11)
    3. Run the algorithm on (1,2) and on (1,11) separately <= again recursion calls. The result is dLmin = infinity and dRmin = infinity
    4. dLRmin = 9
    5. result = min(dLmin, dRmin, dLRmin) = 9