そこで、マイケル・ラビンによるアルゴリズムの詳細を見つけようとしています。このアルゴリズムは、O（n）時間で2Dの点のセットが与えられた場合に最近傍を見つけます。何らかの理由で、グーグル検索は完全に私を失敗させています。私が見つけた最高の（そして唯一の）説明はここにあります：http：//rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/。
誰かがこれについて何か知っているか、主題に関する本や論文をどこで見つけるかを知っているなら（できればオンラインで！）、私はあなたが量り込んでくれて本当に感謝しています。
論文を見つけるのに苦労しているかもしれない理由の1つは、HopcroftとFortuneによるこの回答論文がいくつかの問題に言及しているためだと思います。特に、Rabinのアルゴリズムは、ランダム化を使用してO（n）時間で最も近いポイントを見つけることを目的としています。これが正しく行われている一方で、高速化の本当の理由は、任意の実数から整数フロアへの一定時間の変換を行う機能です。この仮定の下で、HopcroftとFortuneは、平面内の最も近い点を見つけるための決定論的O（n lg lg n）アルゴリズムを提案します。
これがあなたの質問に対する満足のいく答えであるかどうかはわかりませんが、少なくとも上記のリンクはクールなアルゴリズムです！
「最近傍」はくだらない名前でした。これは「最も近いポイントのペアの問題」としてよく知られています。たとえば、http：//en.wikipedia.org/wiki/Closest_pair_of_points_problemは、KhullerとMatiasによるこの単純化を引用しています。http ：//www.cs.umd.edu/ 〜samir / grant / cp.pdf