私は2Dポイントのセットを持っており、どのペアのポイントがセット内で最短距離にあるかを知る最も速い方法を見つける必要があります。ポイント間の最短距離を見つける最速の方法
これを行う最適な方法は何ですか？私のアプローチはクイックソートでそれらを並べ替え、距離を計算することです。これはO（nlogn + n）= O（nlogn）となります。
線形時間で行うことは可能ですか？
ありがとうございました。 O（N^2）内の全ての点のうち
号最小距離あなたが他のすべての点に対してすべての点を比較しなければならないからです。技術的にはn * n/2です。これは、行列の半分を満たす必要があるためです。
与えられた点に最も近い近傍を見つけるアルゴリズムがより高速です。残念なことに、最も近い2つの点を見つけるために、すべての点についてこれを行う必要があります。
この図はアルゴリズムではありません。 Fortune Algorithmがダイアグラムを生成します。 http://en.wikipedia.org/wiki/Fortune%27s_algorithm。これは、ポイントを比較するのではなく、スペースを分割するので、これが当てはまるかどうかはわかりません。 –
点の問題の最も近い一対又は最も近いペア問題がcomputational geometryの問題である：距離空間にN点を与え、最小の距離を有する点のペアを見つけますその間に...
floor functionが一定時間内に計算可能であると仮定する計算モデルでは、問題はO（nログログn）時間。我々はランダム化は床関数と一緒に使用することを許可した場合、問題が
を使用すると、各地点から一定量を精査し、反復深化さDFSを使用することができれば... O（N）時間で解くことができますあなたは2つの最も近いポイントよりも離れてチェックすることは決してありません。あなたが失敗したパスに依存していないので、ID DFSの傾向を再計算する必要はありません。
quicksortで2次元データをどのように並べ替えますか？そして、これは2つの最も近い点を見つけるのにどのように役立ちますか？ –
私はそれらをx座標で並べ替えます。基本的にはhttp://en.wikipedia.org/wiki/Closest_pair_problemで説明されているアルゴリズムを実装したようです。最初にxでソートし、次に分割して征服します。だから、より速い方法がないようです。 –
Xによるソートは、最も近い点に近いX値を持たない可能性があるため、実際の値はまったくありません。また、Xでソートしても、すべての点を他の点と比較して最も近い点を見つける必要はありません。 –