最近接点ペア問題

最近接点ペア問題または最近接ペア問題は、計算幾何学の問題である。${\displaystyle n}$距離空間内の点から、それらの間の距離が最小となる点のペアを見つける。ユークリッド平面内の点の最近接点問題^{[ 1 ]}は、幾何学的アルゴリズムの計算複雑性の体系的な研究の起源において扱われた最初の幾何学的問題の一つであった。

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

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

Rabin (1976)の線形期待時間ランダム化アルゴリズムは、 Richard Liptonによって解析を容易にするために若干修正され、入力セットに対して次のように進行する。${\displaystyle S}$から構成される${\displaystyle n}$ポイント${\displaystyle k}$次元ユークリッド空間：

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

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

代わりに、 Khuller & Matias (1995)の別のアルゴリズムは2 つのフェーズを経ます。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}$ムーア近隣に他の点が存在しないすべての点。

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

最近傍ペア問題の動的バージョンは、次のように記述されます。

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

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

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

• GIS
• 近隣住民検索