Menu
So I'm trying to find details about an algorithm by Michael Rabin, which finds the nearest-neighbor given a set of points in 2D in O(n) time. For some reason, google search is completely failing me. The best (and only) description I've found is here: http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/.
If anyone knows anything about this, or knows where to find a book or paper on the subject (preferably online!), I'd really appreciate you weighing in.
886
In this problem, a set of n points are given on the 2D plane. In this problem, we have to find the pair of points, whose distance is minimum. To solve this problem, we have to divide points into two halves, after that smallest distance between two points is calculated in a recursive way.
It is shown that both of the foregoing problems can be solved by randomized algorithms that useO(n) space and finish inO(n) time with probability tending to 1 asngrows to infinity.
The Brute force solution is O(n^2), compute the distance between each pair and return the smallest. We can calculate the smallest distance in O(nLogn) time using Divide and Conquer strategy.
I think that one reason that you might be having trouble finding the paper is because of this response paper by Hopcroft and Fortune mentioning some issues with it. In particular, Rabin's algorithm purports to use randomization to find closest points in O(n) time, and while it correctly does so the real reason for the speedup is the ability to make constant-time conversions from arbitrary real numbers to their integer floors. With this assumption, Hopcroft and Fortune propose a deterministic O(n lg lg n) algorithm for finding closest points in the plane.
I don't know if this is a satisfactory answer to your question, but at the very least the above link is a cool algorithm!
54
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
