最近点対問題(Closest Pair of Points)

問題の定義

平面上のn個の点の中からユークリッド距離が最小の点の組み合わせを出力する。

実装

ソースコード(Ideone)

解説

• 入力をランダムにシャッフルしたのちに逐次添加アルゴリズムを用いる。
• アルゴリズムが実行される任意の時点において、一辺の長さのメッシュ構造が保たれている。はその時点で発見済みの二点間の最小距離。
• このメッシュ構造においては、最小距離を更新される可能性のある点は、着目している点の周り25個の小正方形内に限られる。
• 計算量は。素朴な実装では、ソートして分割統治するアルゴリズムではであるから驚くべき改善である。