四分木
点四分木は、二分木を2次元座標データを表すように適応させたものである。分割の中心点には常に1つの点データが対応する。木構造の形状はデータを処理する順序に依存する。2次元座標データ列を効率的に比較することができ、一般的な処理時間は O(log n) である。
幾何学的分割で各象限のアイテム数が減らない場合(データがオーバーラップしている場合など)、四分木による分割は失敗し、アルゴリズムが続く限りメモリを消費し続けることになる。例えば、1つの象限の容量の上限が8の場合、(0, 0) に9つの点があるとすると、分割しても3つの象限は空で、残る1つに9つの点が含まれることになる。従って、再帰的に分割が必要になるが、どこまで分割しても上限を超えてしまう。そのような場合、1つの象限に8個以上の点を許容せざるを得ないので、四分木は任意の幾何学的データ群について O(N) の複雑性に漸近していく。