最近点対問題について語ってみる
2013年6月29日追記：
先に証明した補題の方では実装上遅くなってしまうことが、考えていてわかったので修正しました。
内容は表題の通り。非常に初歩的な内容なのだが、某所で説明した際に、一部の「なぜ？」という疑問に答えられなかったので、その鬱憤を晴らしてみる。
なお、Pythonで実装したコードはここにある。（あとで紹介する補題を適用していないので、このままだと遅い）
参考にしたリンクは以下の通りである。
１．Closest pair of points problem - Wikipedia, the free encyclopedia
２．Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press and McGraw-Hill, 2009. Pages 1039-1043 of section 33.4: Finding the closest pair of points.
（第二版と第三版では載っているページが違うから、注意する）
３．UCSB Lecture Notes
（このスライドの8枚目の方が、Intro. to Algorithmsに載っていて、かつ下に述べる補題についてはわかりやすいと感じた。実装時はこのスライドを参考して、探索する点を境界線上に射影し、各点に対して高々6つの点を探索した方がよい。）
以下二点は面白そうなリンクである。
４．http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep 分割統治法を使用していない方法。ちょっと時間計算量についてまだ考えていないので、不確定
５．面白CS論文紹介まだ元論文を読んでいないが、面白そうなアイディアである。
まず（二次元における）最近点対問題とは何かを定義する。
「ある点集合が与えられた時、その中のある点対に対して、それらの点の間の距離が最小となる距離を求める」ことである。
なおここでの距離の定義はユークリッド距離とする。また、点の数をnとする
例を挙げると、点集合P = [(1,0), (1,3), (1,4), (1,8)]においては点対(1,3)と(1,4)間の距離がとなり、最小である。
最もナイーブな実装では、全ての点対を調べれば良いので時間計算量はO(n^2)であり、メモリ計算量はO(1)である。しかし分割統治法をうまく使うと、メモリ計算量O(n)で、時間計算量O(nlogn)に落とすことができる。以下そのアルゴリズムの概要を述べる。
０．利用する配列はX、Yである。
１．点集合Xと点集合YをそれぞれX軸、Y軸の座標をキーとして、ソートする。もし、Xの点数が＜3ならばペアは一ペアしか存在しないため、そのペア距離を調べ、最短距離を返す。
２．X軸において、中間値x_medianをとり、そこを分割線としてその中間値よりX座標が小さい点はX_l, 大きい点はX_rに分類しておく。なお、X_lに分類された点に対して、Y軸の座標をキーとしてソートされた点集合Y_l、またX_rに対応したY_rも保持しておく。
３．分割された点集合それぞれに対して、最短距離δ_l, δ_rを算出し、その内の小さい方をδとして保持する。
４．ここで問題になるのが、点対の片方がX_lに属し、もう片方がX_rに属しているかつ、その点対の距離がδより小さい場合である。それらの点対間の距離を算出するため、点集合Y_l, Y_rに対して、中間値x_medianの点よりx軸方向に距離δ以内に存在する点を全て取得し、その集合をY'とする。
５．Y'の全ての点pに対し、x軸方向においてδと-δ以内、かつy軸方向に-δ以内の点を取ってくる。そういった点p'に対して、pとp'間の距離δ'が距離δより小さい場合はδ=δ'と値を更新する。なお、後の補題ではそういった点p'が高々7つ（点p自体は含めないため、7つである。より工夫すれば5つ）であることを示す
なお、時間計算量を求める際に問題としては、５．において、pよりδ以内の点がどれだけあるのかが問題になってくる。仮にnこあるとし、Y'の点の最大数をnとすると、O(n^2)になってしまうため、高々定数個であることを言わなければならない。（ちなみにここの部分を説明できなくて詰まってしまった）
補題
ステップ５．において、Y'内の点pより2δ×δ（x軸に2δ、y軸にδ）の長方形内に存在する点はY'内では高々8こである。*1
証明：
中央値x_medianの点は二つ存在するとしたら、最悪のケースは片方の点がX_lに、もう片方の点がX_rに分類されたときである。（この時最短距離δ'は0となるが）。
まずステップ２．において分割された際に、X_lもしくはX_rに含まれる点対は最低でもδ以上である。（δ以下の場合は、その点対が最短距離δとなっているはずである。ただし、点対に内、片方の点がX_lに、もう片方の点がX_rに所属していた場合、点対の距離がδ未満はありうる。このケースをケースAとする。）
すなわち、点pより2δ×δの長方形の各頂点に対応する点であり、自分自身を含めれば、その点は高々8こである。
（なお、上記のケースAの場合、すなわち2δ×δの長方形内に距離δ未満の点対が存在している場合は、点の数は8こより少ない。）
（証明終わり）
実際の実装では、点対間の最短距離δを求めるだけならばδ未満を調べれば良いので、高々7n点を調べれば良い。ゆえに、ステップ５．は時間計算量O(n)で完了する。
ステップ３．における再帰の回数は、二分木の高さと等しいのでlognである。これをnこの点に対する時間計算量T(n)を再帰式で表すと(以下Intro. to Algorithms、1043ページより抜粋)
となる。
この再帰式を解くとT(n) = O(nlogn)となる。（∵ T(2) = 1, T(4) = 2*T(2) + O(n) = 2*1 + O(n), T(8) = 2*(2*1 + O(n)) + O(n), ... T(2^i) = 2^{i-1} + 2(i+1) * O(n)となり、n=2^i より i = lognであるからT(n)=O(nlogn)）なお、一番最初にソートをしているが、(比較）ソートは時間計算量θ(nlogn)で可能なので、時間計算量O(nlogn)に変わりはない。
