拉宾最近邻（最近点对）算法？
因此，我试图找到有关 Michael Rabin 算法的详细信息，该算法在 O(n) 时间内找到给定的一组二维点的最近邻。由于某种原因，谷歌搜索完全让我失望。我发现的最好的（也是唯一的）描述在这里： http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/。
如果有人对此有所了解，或者知道在哪里可以找到有关该主题的书籍或论文（最好是在网上！），我非常感谢您的参与。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为您可能无法找到该论文的原因之一是
我不知道这是否是您问题的满意答案，但至少上面的链接是一个很酷的算法！
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!
“最近的邻居”是个蹩脚的名字。它更广为人知的名称是“最近对点问题”，例如 http://en.wikipedia.org/ wiki/Closest_pair_of_points_problem，其中引用了 Khuller 和 Matias 的简化：http ://www.cs.umd.edu/~samir/grant/cp.pdf
"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