kd-tree

定義

k次元空間を再帰的に半分ずつ軸並行の超平面で分割して整理したデータ構造。各レベルで軸を交互に変えながら中央値で分割を繰り返し、葉に少数の点が収まる木を構築する。クエリ時は木を辿って候補領域を特定し、branch-and-bound（枝刈り）で無関係な領域を除外することで、低次元データに対してO(log N)の最近傍探索を実現する。