kd tree（kd木）を使った近傍点検索

kd tree を使った近傍点検索のメモ。

• kd tree の日本語の説明はkd木 - 日本語版 Wikipedia。
• 近傍点検索の擬似コードがあり、日本語版の元となっているのはkd-tree - 英語版 Wikipedia。
• 実際に動くコードで分かりやすいものは弾さんのところ。404 Blog Not Found:algorithm - 最近点検索をkd-treeで。
• 他には An intoductory tutorial on kd-trees という PDF があるが難しい。

kd tree の構築は、平衡木にするためのロジックがいくつかある事をのぞけばとても簡単。弾さんのコードを読めば分かると思う。
近傍点の検索は k 次元で説明されているものが多く分かりづらいと思った。自分で単純な2次元の場合にして考えれば良い。
流れは以下の通り。

• 検索対象点 p を kd tree 上で binary search tree と同様に検索し leaf node に到達。
• p と leaf node の距離^2 を d とする。
• leaf node が最も近い点かどうかは分からない。
• parent node に上がる。
• p を中心として半径 sqrt(d) の円を考えて、parent node がその円と交わるかどうかを考える。
• 交わらない場合
  • parent node の別の子には最近傍点はないことがわかるので更に parent に上がる。
• 交わる場合
  • 最近傍点が parent node のもう一方の子にある可能性があるの。その子を検索開始 node として検索を再帰的に呼び出す
  • 検索の結果と leaf node の近い方を返し。parent に上がる。

実際の分割図を描き、この説明を読みながら弾さんのコードを追えば理解の助けになると思う。