私は3次元の点のセットを持っています。私はこれらの点のどれかのk最近傍のクイッククエリーをしたい。私はこれを行う通常の方法がoct-treeであることを知っていますが、私は以下のデータ構造でクエリがはるかに高速になると考えています。空間点の最小グラフ
Iは、以下の特性を有する頂点として点に対して最小グラフたい：P2、任意の2点P1と
：全内点P3のためにパスがある：
距離（P1、P3）< =距離（P1、P2）。
私の問題は、手頃な価格でこの最小限のグラフをどのように計算するのか分かりません。
7年後、私は自分の質問に答えることができると思います。
を私が探していたグラフは単調近接グラフと呼ばれている - 最も知られている例では、ドロネー三角形分割/四面体です。
スペースパーティションツリーと比較すると、このようなグラフは検索時間が短縮されますが、メモリが多くなり、縮退の問題により計算に時間がかかり、計算が失敗する可能性があります。
これらの問題のために、私は一般的にKNNクエリをスピードアップするアプリケーションはお勧めできないと思うし、単にkdツリーを使うべきです。
これは、銀色の弾丸がないためです。
前回の計算やバッキングデータ構造がたくさんある高速クエリや、比較的遅いクエリを実行できます。それはあなた次第です。
あなたが求めているように聞こえるのは、ある点から離れている点です。 d（P1、P2）は単なる数値なので、P1からその距離内にあるすべての点が基準を満たします。
検索を何回も実行する必要がある場合や、複数の開始点から検索する必要がある場合は、kdツリーのような標準的なデータ構造を調べる必要があります。あなたが一度だけ実行しているなら、すべてのポイントを反復することがあなたの最善の策かもしれません。
あなたが気にしていたアプリケーションは何でしたか？
あなたは正しいです。より多くの読書をした後、空間的なKNNクエリーのための最善の解決法は、一般的な空間木の解法であると思われる：octreeとkd-tree – libeako
質問が混乱しています。問題の宿題のようなステートメントは、それがグラフアルゴリズムが適用されるグラフ問題のように見える。しかし、実際には2つの頂点間の距離を計算する「空間」と「3次元」に関して質問を始めます。だから、あなたの問題をより良く述べようとしてください。それが宿題であれば、そのようにタグを付けてください。それはそのままですが、この質問は下落したり閉じたりする可能性が非常に高いです。 –
画像が助けになるかもしれませんが、私はまだグラフトラバーサルが良い空間分割ソリューション（すなわちKdツリー）より速くなることに疑問を持っています。 –
これは宿題ではありません。 – libeako