因此，我正在尝试查找有关 Michael Rabin 算法的详细信息，该算法在 O(n) 时间内给定一组 2D 点找到最近邻。出于某种原因，谷歌搜索完全让我失望。我找到的最好的（也是唯一的）描述在这里：http ://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/ 。
如果有人对此有所了解，或者知道在哪里可以找到有关该主题的书籍或论文（最好是在线的！），我非常感谢您参与进来。
问问题
2874 次
2 回答
4
我认为您可能无法找到这篇论文的一个原因是因为Hopcroft 和 Fortune 的这篇回应论文提到了它的一些问题。特别是，Rabin 的算法声称使用随机化在 O(n) 时间内找到最接近的点，虽然它正确地这样做了，但加速的真正原因是能够进行从任意实数到整数下限的恒定时间转换。有了这个假设，Hopcroft 和 Fortune 提出了一种确定性 O(n lg lg n) 算法来寻找平面中的最近点。
我不知道这是否是您问题的满意答案，但至少上面的链接是一个很酷的算法！
于 2011-02-15T21:09:53.200 回答
4
"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
于 2011-02-15T21:15:42.950 回答