平面に点をばらまき、その中で最も近い二点を探す。点が少なければ目で見ても分かるが、大量になると計算の仕方が重要になる。すべての組合せを調べる方法から一歩進むと、幾何学の性質を使って比較を減らせる。
総当たりでは、組合せが急増する
点がn個あれば、異なる二点の組合せはn(n−1)/2通りである。1,000点なら499,500組になる。各組の距離を計算して最小のものを選べば答えは出るが、点の数を増やすと、計算量はおおむねその二乗で増える。
一直線上の点なら、座標順に並べて隣り合う点だけを比べればよい。二次元では、横の座標が近くても縦に遠い点があり、横方向の隣だけを見て済ませることはできない。平面の広がりを扱う工夫が必要になる。
左右に分け、境界を調べる
分割統治法では、横の座標で点を並べて左右に分け、それぞれの側で最も近い二点を求める。得られた二つの距離の小さい方をδとする。左右をまたぐ組でこれより短いものがあるなら、両方の点は分割線の近くにあるはずである。
そこで、分割線から横方向にδ以内の帯へ候補を絞る。さらに縦の座標順に調べ、縦方向だけですでにδ以上離れている点は比べない。左右それぞれの内部では点同士がδ以上離れているため、狭い範囲に候補がいくらでも詰まることはない。
並べ方を引き継ぐことも重要になる
この詰め込みの制約によって、帯の中で一つの点と比較する相手は少数に限られる。分割するたびに縦の順序を一から作り直すのではなく、左右の順序を併合して引き継ぐと、全体をO(n log n)の時間で処理できる。
プリンストン大学のアルゴリズム教材にも、この計算量を持つ最近点対の実装が示されている。速さを生むのは、距離の計算式を少し短くすることではない。答えになり得ない組を、位置関係から比較の前に除くことである。図形の性質が、そのまま計算を節約する根拠になる。
本文は平面上のユークリッド距離を扱う。重複する点があれば最短距離は0になる。道路に沿う距離など、距離の定義が変われば同じ絞り込みをそのまま使えるとは限らない。
参考資料
参考資料確認日：2026年10月14日。