バイナリ空間分割
BSP木は空間を各ノードで2つの部分領域に分割していく。これに関連して、4つに分割する四分木や8つに分割する八分木がある。
ここで、p は使われる分割面の数、s は形成される部分領域の数である。
BSP木は任意の次元の空間に使えるが、四分木と八分木はそれぞれ2次元空間と3次元空間の分割に特化している。これらと似ているが、任意の次元で使えるものとしてkd木がある。