Kd木
kd木が点の代わりに矩形または超矩形を格納する場合がある。2次元の矩形は4次元のオブジェクト (xlow, xhigh, ylow, yhigh) とみなすことができる。したがって、矩形範囲探索は、その矩形範囲に重なる全ての矩形を求める問題となる。木構造は通常、各葉ノードが矩形に対応するように構築される。直交範囲検索では、中央値との比較に反対側の座標値を用いる。例えば、現在のレベルの分割が xhigh に沿って行われているなら、探索矩形の xlow の座標値を用いる。中央値が探索矩形の xlow より小さいなら、左側の分枝には探索矩形と重なるものがないと判断でき、刈り取ることができる。さもなくば、両方の分枝を走査する必要がある。これの1次元の特殊ケースを区間木と呼ぶ。