この問題の単純な解法は,2 点の組すべてについて距離を求めて,その最も小さい値の 2 乗を答として返す方法である.この方法では入力サイズ n の 2 乗のステップ数がかかる.n がそれ程大きくない場合,例えば n≦100 のときはこの方法でも十分であるが,n が問題の範囲内にある 10 万,100 万,1000 万,1 億となってくるとそれぞれ 10 の 10 乗,10 の 12 乗,10 の 14 乗,10 の 16 乗となり,処理に非常に時間がかかる可能性が出て来る.
この問題は「計算幾何学」という分野に関連のある問題であるが,もちろん,計算幾何学の専門知識なしでも効率良いアルゴリズムを考えることはできる.
まず,2 次元の座標データはそのままでは扱うのが難しいので,何らかの構造を入れる(ある特殊なデータ構造に座標データを格納していく)か,または 1 次元に落として考えるとよい.ここでは,後者の方法を考える.
- 先ず,入力データを x 座標の小さい順に並べ替える.そのためには,例えばクイックソートを使う.x 座標の小さい順に並べ替えたデータを順に a[0], a[1], ..., a[n-1] とする.
- a[0] 〜 a[i] (i≧1) に対して,その中での距離の最小値を求め,それを L とする.
- 次に,a[0] 〜 a[i+1] の中での距離の最小値を求める.
a[i+1] と a[0] 〜 a[i] の距離を求めるが,a[i+1] と x 座標が L 以上離れているものは計算しない.また,a[0] 〜 a[i] の中で a[j] が a[i+1] と x 座標が L 以上離れているならば a[0] 〜 a[j-1] も L 以上離れているので,それらについては a[i+1] と x 座標が L 以上離れているかのチェックもしない.
このように調べる範囲を制限して,L よりも小さいものが見つかればそれに置き換えていく.
- 以上の 2. 〜 3. を a[0] 〜 a[n-1] になるまで i を増やしながら繰り返し,距離の2乗を返す.
この解法でも,最悪のときは,入力サイズ n の 2 乗のステップ数がかかことがあるが,平均的には効率的と思われる.