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

Asked 15/2, 2011 at 20:58 Answered 15/2, 2011 at 21:15

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.

Dominiquedominium answered 15/2, 2011 at 20:58 Comment(1)

It was originally published in "Algorithms and Complexity" in the year 1976. There does not seem to be any online version of that. – Rubious 15/2, 2011 at 21:17

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!

Mew answered 15/2, 2011 at 21:9 Comment(0)

"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

Saintpierre answered 15/2, 2011 at 21:15 Comment(0)

Recommended topics

Hot tags