CODEWITHSUNDEEP
algorithmclosest
Aaron
Aaron

Reputation: 105

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?

Upvotes: 7

Views: 8519

Answers (4)

ibodi
ibodi

Reputation: 1776

Maybe Linear-time Randomized Closest Pair algorithm will help. There you can find the pair in expected time O(n).

Upvotes: 0

Antti Huima
Antti Huima

Reputation: 25542

the basic idea of the algorithm is this.

You have a set of points P and you want to find the two points in P that have the shortest distance between them.

A simple brute-force approach would go through every pair in P, calculate the distance, and then take the one pair that has the shortest distance. This is an O(n²) algorithm.

However it is possible to better by the algorithm you are talking about. The idea is first to order all the points according to one of the coordinates, e.g. the x-coordinate. Now your set P is actually a sorted list of points, sorted by their x-coordinates. The algorithm takes now as its input not a set of points, but a sorted list of points. Let's call the algorithm ClosestPair(L), where L is the list of points given as the argument.

ClosestPair(L) is now implemented recursively as follows:

  1. Split the list L at its middle, obtaining Lleft and Lright.
  2. Recursively solve ClosestPair(Lleft) and ClosestPair(Lright). Let the corresponding shortest distances obtained by δleft and δright.
  3. Now we know that the shortest distance in the original set (represented by L) is either one of the two δs, or then it is a distance between a point in Lleft and a point in Lright.
  4. Se we need still to check if there is a shorter distance between two points from the left and right subdivision. The trick is that because we know the distance must be smaller than δleft and δright, it is enough to consider from both subdivisions points that are not farther than min(δleft, δright) from the dividing line (the x-coordinate you used to split the original list L). This optimization makes the procedure faster than the brute-force approach, in practice O(n log n).

Upvotes: 9

Howard
Howard

Reputation: 39207

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

Upvotes: 7

Nikita Rybak
Nikita Rybak

Reputation: 68016

I think I know what algorithm you're talking about. I could recount it here myself, but the description given in Introduction to Algorithms is by far superior to what I can produce. And that chapter is also available on google books: enjoy. (Everybody else can find problem description there too)

Upvotes: 2

Related Questions