Rabin's最近邻（最接近的点）算法？

Question

我正在寻找关于Michael Rabin的算法的详细信息，该算法可以在O(n)时间内给出2D点集中的最近邻。不知为何，谷歌搜索完全无法帮到我。我找到的最好（也是唯一）的描述在这里：http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/。

如果有人了解此事或知道在哪本书或论文中可以找到相关内容（最好在线！），我真的很感激您的帮助。

- Andy Shulman

---

它最初是在1976年的《算法和复杂性》中发表的。似乎没有任何在线版本。 - Aryabhatta

Answer 1

我认为你找不到这篇论文的原因之一是由于Hopcroft和Fortune在这篇回应论文中提到了一些问题。具体而言，Rabin的算法声称使用随机化以O(n)的时间找到最接近的点，虽然它确实做到了，但加速的真正原因是能够将任意实数转换为其整数下取整的能力。基于这个假设，Hopcroft和Fortune提出了一种确定性的O(n lg lg n)算法来寻找平面上最接近的点。

我不知道这是否对您的问题有满意的答复，但至少上面的链接是一个很酷的算法！

- templatetypedef

Answer 2

“最近邻”这个名称有点糟糕。它更为人所知的是“最近点对问题”，例如，http://en.wikipedia.org/wiki/Closest_pair_of_points_problem，该网页引用了Khuller和Matias的简化版本：http://www.cs.umd.edu/~samir/grant/cp.pdf。请注意，本文中的HTML标签已保留，但不包含解释。

- userOVER9000