I'm sure most are familiar with the closest pair problem, but is there another alogrithm or a way to modify the current CP algorithm to get the next closest pair?
+1
A:
Easy one, in O(n log(n)) :
- find the closets pair (p1,p2) in O(n log(n))
- compute all pairs with p1 or p2 (but not (p1,p2)) keep the closest one, let's call it
Ein O(n) - remove p1 and p2 in (1)
- find the closets pair, compare it to
Eand keep the closest one, again in O(n log(n))
You now have the second closest one.
Loïc Février
2010-10-26 20:53:31
Do you know if there is an efficient way to generalize this process so you can obtain the kth closest pair? Preferably in a way that is not O(n!)?
Tyler Murry
2010-10-27 20:10:33
I wonder how you compute the fourth step in O(n) :)
Dimitris Andreou
2010-10-29 05:13:51
@Dimitris : indeed, `O(n log(n))` of course......
Loïc Février
2010-10-29 11:08:39
@Tyler : just do k times the processus, so `O(k.n.log(n))`
Loïc Février
2010-10-29 11:09:18