algorithm - 拉宾的最近邻(最近的一对点)算法？

Question

因此，我正在尝试查找有关 Michael Rabin 算法的详细信息，该算法在 O(n) 时间内找到给定一组二维点的最近邻点。出于某种原因，谷歌搜索完全让我失望了。我找到的最好的(也是唯一的)描述在这里:http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/ .

如果有人对此有所了解，或者知道在哪里可以找到有关该主题的书籍或论文(最好是在线!)，我将非常感谢您的参与。

Answer 1

我认为您可能无法找到论文的一个原因是 this response paper by Hopcroft and Fortune提到一些问题。特别是，Rabin 的算法声称使用随机化在 O(n) 时间内找到最近的点，虽然它正确地这样做了，但加速的真正原因是能够从任意实数到整数层进行恒定时间转换。在此假设下，Hopcroft 和 Fortune 提出了确定性的 O(n lg lg n) 算法来寻找平面中的最近点。

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