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