これは Competitive Programming Advent Calendar Div2013 の 20 日目の記事です.最近点対問題の話をします. 最近点対問題は,空間上に点の集合が与えられた時に,その中で最も距離が近いペアを探す問題です. 応用としては,何らかのオブジェクトを特徴ベクトルに写した後で,最も類似したペアを探したいときなどに役に立つのではないかと思います.競技プログラミング界では,今年のICPC会津大会で3次元上の最近点対問題が出題されました. 空間が平面のときは分割統治による $O(n\log{n})$ 時間アルゴリズムが有名かと思います.今回は一般の次元で,(ハッシュマップを用いて)線形時間で動く実装が楽そうな乱択アルゴリズムの紹介をします.参考にした文献は以下のサーベイです. Smid, Michiel. Closest point problems in c