【ケーディーぎ】
k-d木 とは？
公開:
💡 縦、横と領域を分けて、探さなくてよい場所を減らす
複数の座標を持つ点を、軸に沿う境界で再帰的に二分する木構造。範囲内の点や近くの点を探す際、関係しない領域を候補から外すために使う。
📌 このページのポイント
- kは扱う座標の次元数であり、子ノードの数ではない
- 2次元の基本例では、x軸・y軸の座標を交互に使って二分する
- 探索性能は点の配置や次元数に依存し、最近傍探索が常にO(log n)とは限らない
ひよこ k個に枝分かれする木なの？
ペンギン先生 kは座標の次元数だよ。平面上の点ならxとyで2次元。基本的なk-d木は、選んだ座標の値を境に領域を二つに分ける二分木なんだ。
ひよこ 平面ではどう分けるの？
ペンギン先生 たとえば最初はx＝5で左右に分け、左の領域をy＝4、右をy＝6で上下に分ける。図はこの3回の分割の例だよ。x座標とy座標を交互に使うのが基本形の一つで、実装によって軸の選び方は変わるんだ。
ひよこ 近い点は、同じ領域だけ探せばよい？
ペンギン先生 それでは見落とすことがあるよ。境界のすぐ向こうにもっと近い点があるかもしれないんだ。まず近そうな側を調べ、ほかの領域までの最短距離を使って、その領域に現在の候補より近い点があり得るか判断するよ。
ひよこ 二分するから、いつでも速い？
ペンギン先生 片寄った木や点の配置によっては、多くの領域を調べる必要があるよ。最近傍探索は最悪では全点に及ぶこともある。中央値を使って木の高さを抑える工夫と、探索時に領域をうまく除外できるかは別の問題なんだ。
もっと詳しく知りたい人へ
地図の緯度・経度や高次元の特徴量にもそのまま使えますか？
使う距離とデータの性質を確認します。緯度・経度上の単純な平面距離は、地球上の距離と一致しません。高次元では候補を十分に除外できなくなる場合もあり、木を使うだけで高速化が保証されるわけではありません。
まとめ：ざっくりこれだけ覚えればOK！
「k-d木」って出てきたら「座標軸で空間を二分し、点の探索を絞り込む木」と思えればだいたいOK！