2次元平面上のn点を考えると、各点のk個の最近傍点を見つける必要があります。

Question

min-heapを使った方法を調べました。各点について、サイズkの最小ヒープを格納することができますが、それは大きなn（1億の周りのnを対象とする）にはあまりにも多くのスペースを必要とします。確かに、より少ないスペースを利用し、時間の複雑さにそれほど影響を与えない、これを行うためのよりよい方法がなければなりません。他のデータ構造はありますか？

Answer 1

この問題は、KD-treeの一般的な設定です。そのような解は直線的な複雑さを有するが、実装するのが比較的複雑な場合がある（準備が整った実装が利用できない場合）

別の方法として、ナイーブアルゴリズムの複雑さを減らすためにバケットを使用することができる。アイデアは、平面を「バケット」、すなわちあるサイズの四角形に分割し、それらが属するバケット内にポイントを配置することです。最も近いポイントは最も近いバケットからのものです。ランダムなデータの場合、これはかなり良い改善になる可能性がありますが、最悪の場合は未知のアプローチと同じです。