ポイントA、Bの2つのセットがあり、セットAのすべてのポイントについて、セットBの最近傍を見つけたいとします。
1つのポイントの最近傍を見つけるための優れたアルゴリズムはたくさんあります。a_1について取得した情報を使用して、セット内のa_2または他のポイントの最近傍をより効率的に検索する方法はありますか？
私は次のようなことを考えています：三角形の不等式を使用して、Bのすべての点と新しい点a_2の間の可能な距離の間隔を取得し、間隔の最大値と最小値を並べ替えると、Bの点に該当する点のみを検索できます最初の間隔。
手順2の詳細：現在スイープラインと交差しているボロノイ図のすべてのエッジを、順序付けられたコンテナに保持します。スイープラインがボロノイ図の頂点をカバーしている場合、この頂点に付随するエッジをコンテナから/コンテナに削除/追加します。どのエッジの間にあるポイントが配置されているかを確認するには、コンテナ内のこのポイントまでの後続/先行エッジを取得します。
時間計算量はO（（M + N）log M）です。N = | A |、M = |B|。
巡回セールスマンプログラムのケーススタディを扱っているベントレーの「効率的なプログラムの作成」を読むことでメリットが得られる場合があります。彼が認識した節約の1つは、2つのポイントの違いが、高価な平方根を取ることでした。平方根を取ると実際の距離が得られますが、平方根を取らないと他の相対値と比較するために使用できる数値が得られます。
その本を読むことを強くお勧めします。それはあなたの脳を正しい場所に置きます。
強引な解決策は、セットBの最も近いポイントのデンドグラムを使用することです。次に、セットAの各ポイントをデンドグラムと比較します。ドロネー三角形分割を使用して樹状図を作成することもできます。