Rabin's Nearest Neighbor (Closest pair of points) Algorithm?

Question

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.

Answer 1

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!

Answer 2

"Nearest neighbor" was a crappy name. It's better known as the "Closest pair of points problem", e.g., http://en.wikipedia.org/wiki/Closest_pair_of_points_problem, which cites this simplification by Khuller and Matias: http://www.cs.umd.edu/~samir/grant/cp.pdf