Rabin Nearest neighbor (closest pair of points) Algorithm?

Question

So, I'm trying to find details about the Michael Rabin algorithm, which finds the closest neighbor by setting a lot of points in 2D in O (n) time. For some reason google search completely fails. The best (and only) description I have 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 article on this subject (preferably online!), I would really appreciate that you weigh.

Answer 1

I think one of the reasons you might find it difficult to find an article is this report from Hopcroft and Fortune , which mentions some issues with This. In particular, Rabin’s algorithm involves using randomization to find the nearest points in O (n) time, and although he does it right, the real reason for the acceleration is the ability to do constant time transformations from arbitrary real numbers to their integer floors. With this assumption, Hopcroft and Fortuna propose a deterministic algorithm O (n lg lg n) for finding the nearest points on the plane.

I do not know if this is a satisfactory answer to your question, but at least the above link is a cool algorithm!

Answer 2

"Nearest Neighbor" was a crappy name. It is better known as the “Nearest Two-Point Problem,” for example http://en.wikipedia.org/wiki/Closest_pair_of_points_problem , in which this simplification is quoted by Huller and Matthias: http://www.cs.umd.edu/~samir /grant/cp.pdf