拉賓最近鄰（最近點對）算法？

所以我試圖找到邁克爾拉賓的算法的細節，它發現最近鄰居在O（n）時間給定一組2D點。出於某種原因，谷歌搜索完全失敗了我。我發現的最好的（也是唯一的）描述在這裏：http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/。拉賓最近鄰（最近點對）算法？

如果有人知道這事，或者知道哪裏可以找到關於該主題的書或論文（最好是在線！），我會很感激你的體重。

來源

2011-02-15 Andy Shulman

它最初發表在1976年的「算法和複雜性」中。似乎沒有是任何在線版本。 – 2011-02-15 21:17:36

我認爲其中一個原因，你可能無法找到該文件是因爲this response paper by Hopcroft and Fortune提及它的一些問題。特別是Rabin的算法意圖使用隨機化在O（n）時間內找到最接近的點，而正確地做到這一點，加速的真正原因是能夠進行從任意實數到整數樓層的恆定時間轉換。通過這個假設，Hopcroft和Fortune提出了一種確定性的O（n lg lg n）算法，用於查找飛機中最近的點。

我不知道這是否是您的問題的滿意答案，但至少上面的鏈接是一個很酷的算法！

來源

2011-02-15 21:09:53 templatetypedef

「最近的鄰居」是一個蹩腳的名字。它被稱爲「最接近的一對點問題」，例如http://en.wikipedia.org/wiki/Closest_pair_of_points_problem，它引用了Khuller和Matias的這種簡化：http://www.cs.umd.edu/~samir/grant/cp.pdf

來源

2011-02-15 21:15:42 userOVER9000

拉賓最近鄰（最近點對）算法？

回答

相關問題