最も近い点のペアの問題

最近接点対問題または最近接対問題は計算幾何学の問題です。距離空間内の点が与えられた場合、それらの間の距離が最小となる点のペアを見つけます。ユークリッド平面上の点の最接近対問題^{[1]は、幾何学アルゴリズムの}計算複雑さの体系的な研究の始まりに扱われた最初の幾何学的問題の 1 つでした。 ${\displaystyle n}$

漸近解析の目的で次元が定数として扱われるユークリッド空間において、線形時間で問題を解くランダム化アルゴリズムが知られています。^{[2] [3] [4]}これは、すべての点のペア間の距離を見つけて最小のものを選択する単純なアルゴリズムによって得られる時間（ここではビッグオー記法で表されます）よりも大幅に高速です。 ${\displaystyle O(n^{2})}$

ランダム化を行わずに、床関数の使用を許可する無制限のメモリを備えたランダムアクセスマシン の計算モデルで、ほぼ線形時間で問題を解くことも可能です。 ^[5]代数決定木などのさらに制限された計算モデルでは、問題はいくらか遅い時間制限で解くことができ、^[6]これは、要素の一意性の問題からの削減によって、このモデルに最適です。この遅い時間制限を持つスイープラインアルゴリズムと分割統治アルゴリズムの両方が、これらのアルゴリズム設計手法の例として一般的に教えられています。^{[7] [8]}${\displaystyle O(n\log \log n)}$${\displaystyle O(n\log n)}$

リチャード・リプトンが分析を容易にするためにわずかに修正したラビン（1976）の線形期待時間ランダム化アルゴリズムは、次元ユークリッド空間内の点からなる入力セットに対して次のように進行します。 ${\displaystyle S}$${\displaystyle n}$${\displaystyle k}$

1. 点のペアを復元ありで一様にランダムに選択し、選択されたペアの最小距離を とします。${\displaystyle n}$${\displaystyle d}$
2. 入力ポイントを、サイズ（隣接するグリッド ポイント間の距離）が であるポイントの正方グリッドに丸め、ハッシュ テーブルを使用して、同じグリッド ポイントに丸められる入力ポイントのペアを収集します。${\displaystyle d}$
3. 各入力ポイントについて、同じグリッド ポイントに丸められるか、周囲のグリッド ポイントのムーア近傍内の別のグリッド ポイントに丸められる他のすべての入力までの距離を計算します。${\displaystyle 3^{k}-1}$
4. このプロセス全体で計算された距離のうち最小の距離を返します。

このアルゴリズムは、距離が近いペアを同じグリッドポイントまたは隣接するグリッドポイントにマッピングするため、常に最も近いペアを正しく決定します。アルゴリズムの最初のステップでペアを均一にサンプリングすることで（同様の数のペアをサンプリングするラビンの別の方法と比較して）、アルゴリズムによって計算される距離の期待値が線形であることの証明が簡単になります。^[4]${\displaystyle d}$

代わりに、Khuller & Matias (1995) の異なるアルゴリズムでは、2 つのフェーズが実行されます。1 つは、最も近い距離をの近似率内で近似するランダム反復フィルタリング プロセスで、もう 1 つは、この近似距離を正確な最も近い距離に変換する最終ステップです。フィルタリング プロセスでは、 が空になるまで、以下のステップが繰り返されます。 ${\displaystyle 2{\sqrt {k}}}$${\displaystyle S}$

1. から一様にランダムに点を選択します。${\displaystyle p}$${\displaystyle S}$
2. から の他のすべての点までの距離を計算し、 がそのような距離の最小値であるとします。${\displaystyle p}$${\displaystyle S}$${\displaystyle d}$
3. 入力ポイントをサイズ の正方グリッドに丸め、ムーア近傍に他のポイントがないすべてのポイントを削除します。${\displaystyle d/(2{\sqrt {k}})}$${\displaystyle S}$

このフィルタリング処理によって求められるおおよその距離は、が空になる前のステップで計算されたの最終値です。各ステップでは、最も近い近傍が距離以上離れているすべてのポイント（期待値の半分以上）が削除されます。これにより、フィルタリングの合計予想時間は線形になります。 のおおよその値がわかれば、それをラビンのアルゴリズムの最終ステップで使用できます。これらのステップでは、各グリッドポイントに定数個の入力が丸められるため、時間はやはり線形になります。^[3]${\displaystyle d}$${\displaystyle S}$${\displaystyle d}$${\displaystyle d}$

最近接ペア問題の 動的バージョンは次のように述べられます。

• 動的なオブジェクト セットが与えられた場合、オブジェクトが挿入または削除されるたびに最も近いオブジェクトのペアを効率的に再計算するためのアルゴリズムとデータ構造を見つけます。

すべての点の境界ボックスが事前にわかっていて、定数時間のフロア関数が利用できる場合、期待される時間の挿入と削除、および定数のクエリ時間をサポートする期待される空間データ構造が提案されました。代数決定木モデル用に変更すると、挿入と削除には期待される時間が必要になります。^[9]上記の動的最近接ペアアルゴリズムの複雑さは次元で指数関数的になるため、このようなアルゴリズムは高次元の問題にはあまり適していません。 ${\displaystyle O(n)}$${\displaystyle O(\log n)}$${\displaystyle O(\log ^{2}n)}$${\displaystyle d}$

次元空間における動的最近接ペア問題のアルゴリズムは、1998年にセルゲイ・ベスパミャトニクによって開発されました。^[10]ポイントは、ポイントごとに時間内に挿入および削除できます（最悪の場合）。 ${\displaystyle d}$${\displaystyle O(\log n)}$

• 地理情報システム
• 最近傍探索