この質問の詳細ですが、より多くの制約があります。
考え方は同じで、2 ユークリッド次元の k 最近傍点の単純で高速なアルゴリズムを見つけます。データを適切に分割するグリッド サイズを見つけることができれば、バケット グリッドはうまく機能するようです。ただし、データが均一に分散されておらず、密度が非常に高い地域と非常に低い地域 (たとえば、米国の人口) があり、固定されたグリッド サイズでは十分な近隣と効率の両方を保証できない場合はどうなるでしょうか? この方法はまだ救済できますか？
そうでない場合は、他の提案が役に立ちますが、kd-trees などに移動するよりも簡単な答えを期待しています.
あまりにも多くの要素がない場合は、それぞれを他のすべてと比較してください。これは、思ったよりもはるかに高速です。今日のマシンは高速です。残念ながら、二乗係数は遅かれ早かれあなたを捕まえるでしょう。100 万個のオブジェクトを線形検索してもそれほど時間はかからないと思うので、最大 1000 個の要素で問題ないかもしれません。グリッドやストライプを使用すると、その数が大幅に増加する可能性があります.
しかし、あなたは四分木 (kd ツリーの特定の形式) に固執していると思います。マップ全体が 1 つのブロックで、4 つのサブブロック (左上、右上、左下、右下) を含めることができます。線形検索を実行するよりも多くの要素でブロックがいっぱいになった場合は、ブロックをより小さなブロックに分割して、要素を転送します。(葉ノードのみが要素を持ちます。) 特定の点から特定の半径内を検索するのは簡単です。一番上から始めて、ブロックの一部がポイントの範囲内にある場合は、サブブロックがある場合と同じ方法でチェックアウトします。そうでない場合は、その要素を確認してください。
（「最も近い」を検索するときは注意してください。正方形のグリッドは、より近いオブジェクトがより遠いブロックにある可能性があることを意味します。指定された半径内にすべてを取得する必要があります。次に、すべてをチェックします。最も近い 10 個と半径が必要な場合20 個中 5 個しか拾えなかったので、より大きな半径を試す必要があります. 30 離れていることが証明された拒否されたアイテムがあり、10 を補うためにそれと他のいくつかをつかむ必要があると思うかもしれません.ブロック全体が拒否された 25 離れたアイテムで、代わりにそれらが必要です.これにはもっと良い解決策があるはずですが、私はまだそれを理解していません.半径を推測し、それが得られるまで2倍にします.足りる。）
四分木は楽しいです。データをセットアップしてアクセスできる場合は、簡単です。誰が何に近づいているかを把握しようとしているときに、マップされた要素が表示されたり、消えたり、移動したりすると、問題が発生します。
これを見たことがありますか？
http://www.cs.sunysb.edu/~algorith/major_section/1.4.shtml
kd-tree は実装が非常に簡単で、標準の Java/C 実装があります。
また：
ここに質問を投稿してください: