クアッドツリー（四分木）

1974年にラファエル・フィンケルとジョン・ベントリーが発表した。物体はそれを収める最小の象限に入り、領域検索は重なるノードだけを訪れる。全組み合わせの比較が二乗の手間から対数の手間に落ちる。

2Dゲーム、地理情報システム、画像圧縮、衝突判定のブロードフェーズで見かける。「ルース」クアッドツリーでは、境界をまたぐ物体を分割せず親ノードに残す。物体が動くたびの高価な再振り分けを避けられる。