ポイントセットから最も離れた場所を見つけて、クエリポイントから遠く離れた位置に配置することについて多くの質問に答える必要があります。私が今までに見つけたすべてのアプローチは、このケースではうまくいきません（たとえば、k-dツリーにはクエリごとにO（N）があるかもしれません）、またはVoronoiダイアグラムを使用する必要があります。
このようなタスクのために設計された既知のアルゴリズムはありますか？3Dクエリポイントの最近傍点が点集合から遠く離れている
ここでの問題は距離です。クエリがあなたのデータセットから遠い場合、kd-treeは多くの点をチェックしなければならないので、クエリ時間が遅くなります。
あなたが直面しているシナリオは、Nearest Neighbor Structures（一般的なケースではありません）には難しいですが、私があなただったらBalanced Box-Decomposition treesというショットを付けました。データ構造。
いくつかの多次元インデックスには、特にk == 1の場合に、必要に応じて簡単に適応できるkNNクエリがあります。kNNアルゴリズムは、通常、最初に近似近似距離を推定する必要があり、次に、この距離を使用して範囲クエリを実行します。 Rツリーまたはクオッドツリーでは、この推定は、検索ポイントに最も近いノードを見つけることによって効率的に実行できます。次に、最も近いノードから1点を取り出し、探索点までの距離を計算し、この距離に基づいて範囲クエリを実行します。通常、k> 1であるため、いくつかの乗数が使用されます。 これは、検索ポイントが遠く離れていても合理的に効率的でなければなりません。
1点のみを検索している場合（k = 1）、このアルゴリズムを使用して、見つかった最も近い点に正確に基づく範囲クエリを使用できます。
Javaを使用している場合は、オープンソースの実装hereを使用できます。 PH-Tree（クアッドツリーの一種ですが、より効率的で読み込みが高速です）があり、同じkNNアプローチを使用しています。
あなたがk-NN問題を解こうとしていて、 'k 'を大きすぎると設定していることを意味しますか？または、クエリはポイントセットから遠く離れたmuuuuchですか？ – gsamaras
私は、互いに比較的近いポイントの雲があることを意味します。しかし、このクラウドから遠いところにある私のクエリポイントは、すべてのクラウドポイントが（0; 0; 0）とエッジサイズ1でキューブ内にあり、クエリポイントが（2; 0; 0）、（4; 1; 3）など）。 K-dツリーや他の典型的なツリーは、この場合、クエリに答えるのに時間がかかりすぎるとうまくいきません。 – Inspiration
k << nのk個の井戸分布点のサブセットのみでボロノイ図を作成する方法はありますか？クエリでは、log（k）にVoronoiセルを配置してから、この領域の点でkd-tree検索を行います（そのような点のO（n/k）付近にあるはずです）。 – geoalgo