Spaghetti Source - 領域探索 (kd 木)

説明 点の集合が与えられる．領域が与えられたとき，その領域に含まれる点をすべて報告せよ．という問題を領域探索問題という．これは点位置決定問題の双対問題である．幾何学的な問題だけでなく「年齢 20～30 歳，年収 500～1000 万の人をすべて探せ」などのデータベース問い合わせもこの問題に帰着する． この問題を解くために使える構造が kd 木である．これは一次元における二分探索木の拡張であって，探索木の各段階で x における比較，y における比較を切り替えるものである．点が一様に散らばっている場合，二分探索木と同様に平均計算量 O(log n) となる． 以下では問い合わせ領域は直交領域，すなわち x 軸と y 軸に平行な辺をもつ長方形に限っている．しかしどんな形状の領域でも，bounding box をとるなどしてそれが半平面のどちらに位置するかを高速に判定できれば問い合わせ可能である．