algorithm - 空間点の最小グラフ

Question

私は3次元の点のセットを持っています。これらのポイントのいずれかの k 最近傍点の簡単なクエリが必要です。これを行う通常の方法はオクトツリーであることは知っていますが、以下に説明するデータ構造を使用すると、クエリははるかに高速になると思います。

---

次のプロパティを持つ頂点としてのポイントの最小限のグラフが必要です。

任意の 2 点 P1、P2 の間には、すべての内部点 P3 に対して次のパスがあります。

距離 (P1、P3) <= 距離 (P1、P2)。

---

私の問題は、手頃な時間でこの最小限のグラフを計算する方法を理解できないことです。

Answer 1

あなたが求めているのは、別のポイントからある程度の距離内にあるポイントだけのようです。d（P1、P2）は単なる数値であるため、P1からその距離内にあるすべてのポイントが基準を満たします。

複数の開始点から何度も検索を実行する必要がある場合は、kdツリーなどの標準のデータ構造を調べる必要があります。一度だけ実行する場合は、すべてのポイントを繰り返すだけが最善の策かもしれません。

あなたが考えていたアプリケーションは何でしたか？

Answer 2

7年後、私は自分の質問に答えられると思います：

---

私が探していたグラフは、単調近接グラフと呼ばれます。最もよく知られている例は、ドロネー三角形分割/四面体化です。

スペースパーティションツリーと比較して：このようなグラフは、クエリ時間を短縮しますが、より多くのメモリを必要とし、より多くの時間を要し、縮退の問題のために計算が失敗する可能性があります。

これらの問題があるため、一般的に、KNNクエリを高速化するためのアプリケーションはお勧めできません。単に、kdツリーを使用する必要があります。

Answer 3

それは特効薬がないからです。

以前の計算を行わずに比較的低速なクエリを実行することも、以前の計算とバッキング データ構造を多数使用して高速なクエリを実行することもできます。選択するのはあなた次第です。