最も近いユークリッド距離のための効率的なデータ構造

Question

次のUVA問題に触発されています。 HTTPS ：//onlinejudge.org/index.php？option=オンラインジュッジ＆アンプ; itemid= 99999999＆category= 18＆page= show_problem＆問題= 1628

Amazonの地域の気候を監視するために、自律型、バッテリ駆動のデータ収集ステーションのネットワークが設置されています。順序ディスパッチステーションは、それらがそれらの現在のパラメータを変更するように制御ステーションへの命令の送信を開始することができる。バッテリの過負荷を回避するために、各ステーション（順序ディスパッチステーションを含む）は他の2つのステーションにのみ送信できます。駅の先住民は2つの最も近い駅です。描画の場合、最初の基準は西側（地図上の左端）を選び、第2の基準は最南端（地図上で最低）を選ぶことです。 あなたはAmazon State Governmentによって、各ステーションのローカライゼーションを考えると、メッセージがすべての局に到達できるプログラムを書くために、Amazon State Governmentによって依頼されています。

ナイーブアルゴリズムもちろん、頂点としての局を持つグラフを構築し、最も近い2つの他のすべての頂点を検索することによって、特定の頂点からエッジを計算します。その後、DFS / BFSを単純に実行できます。もちろん、これは $ o（v ^ 2）$ 時間（テストケースを渡します）を作成します。ただし、私たちの質問は、適切なデータ構造を使って早くグラフを構築できる場合です。具体的には、任意のクエリポイント $ p $ 、与えられたポイントセット $ s $ です。 $ s $ $ s $ のポイントを整理します。 SPAN> $ p $ （ $ \ log v $ 時間？）。

Answer 1

これを正しく理解した場合、ほとんどの空間インデックスを使用することができます。

空間インデックスは通常、 $ o（log {v}）$ 挿入時間と最寄りの隣人のための類似のルックアップ時間です。 もちろんVoronoiダイアグラムを作成できますが、インデックスを直接使用して必要なときに最も近い隣接者を見つけることもできます。

低次元（2D、3D）の場合、空間インデックスの一般的なファミリーは kd-trees （非常にシンプルで一般的に良いですが、ポイントの密集したクラスターに問題がある傾向があります）、 Quadtree （数値精度がトリッキーな可能性があるために自分自身を実装するのは少し難しい）と R-Tree （実装するのが最も難しいですが、最高の保証されたパフォーマンス、特にR *ツリー（R-STAR-TREE））。

C ++を使用している場合は、 libspatialIndex またはブーストRツリー。 Javaを使用している場合は、 tinspin ライブラリを見てください。

この技術用語は " $ k $ 最近傍クエリ"または " $ k $ -nnクエリ "、 $ k $ 見つけたい最寄りの隣人の数を参照してください。

Answer 2

関連データ構造は動的 voronoi図

ボロノイ図は、平面上の一連の点が含まれているときの答えがよくあります。

ポイントセットが進化しているため、動的バージョンが必要です。