ポイントが与えられると、それに最も近いポイントを見つける空間データ構造（aK-D treeやaなど）を書き込もうとしています。QuadTreex
上記のデータ構造の問題は、それらが主に放射状/領域検索をサポートしていることです。yしたがって、指定されたポイント/ノードの半径内にあるポイントを取得します。
これらの構造を変更して、必要なものを検索するのは非効率的です。x短い半径距離から始めて、放射状検索を数回繰り返し、指定されたポイントに近い必要な数のポイントが得られるまで、それを増やし続ける必要があると想定しています。もちろん、これはデータ構造の背後にある目的全体を無効にします。
ほとんどすべての空間データ構造は、放射状検索で動作します。、または私が意味することを達成するために考慮する必要がある他の空間データ構造に適用できる他の効率的な検索方法は何ですか？QuadTree助言がありますか？
私はあなたがあなたの仮定に正しいかどうかわかりません。kd-treesに関するウィキペディアの記事はx、構造を使用して、検索ポイントに最も近い近傍を見つけることをサポートする方法を示しています。はい、それは本質的に最も近い隣接x時間を見つけることの繰り返しですが、アルゴリズムからより効率的なパフォーマンスを期待する権利があるかどうかはわかりませんkd-tree。
それだけでは不十分な場合は、ポイントを別のデータ構造に格納する必要があります。が小さく、境界がある場合xは、エッジの重みがもちろんポイント間の距離である重み付きグラフにポイントを格納できます。
xが小さくも制限もされていない場合は、空間をk*m均一なセルに単純に分割することができます（ここでは2D、必要に応じて3 + Dに膨らませます）。各検索ポイントについて、それを含むセルに直接移動し、同じセル内の他のポイントを見つけます。それらのいずれかがセルの境界よりも検索ポイントに近い場合x、それらはあなたが探しているものです。そうでない場合は、近くの境界の反対側のセルも検索します。
ラジアル/リージョン検索とxに最も近いネイバー検索の両方をサポートする必要がある場合、各タイプのクエリをサポートする2つのデータ構造を維持する必要があるのは世界の終わりではありません。多くの検索問題の場合、効率的な解決策への最初のステップは、効率的な検索のためにデータを適切な構造に配置することです。この決定は、あなたが単に私たちに提供していない数字に依存します。
四分木で検索メソッドを数回呼び出す場合（これは私が数回行ったことです）、正しいポイント数が得られるまで各呼び出しで検索半径を2倍にすると、検索はそれほど非効率的ではありません。 。
2次元空間を想定し、X点を含む正しい最小半径がR1であり、それらを含む半径R2が見つかるまで倍増し続ける場合、（a）R2は2xR1未満である必要があり、（b）検索される領域検索ごとに4倍大きくなります。これにより、検索した領域の半分だけが実際には不要（またはその周辺）になるという最悪のシナリオが得られます。