Z階数曲線
Z階数曲線の応用により4分木を効率的に構築できる。基本戦略としてz値に基いた並べ替えを施す。一度この並べ替えを済ませれば、格納されたデータに対し直接的に2分木探索を行える線形4分木構造となる。
通常、入力点群は次元ごとに正の整数へ正規化し機械語が対応するサイズとするが、範囲 [ 0, 1 ] の固定小数点表現とする事もある。何れにせよ最上位の非零のビットは定数時間で探索可能となる。4分木の内包する4つの正方形は辺の長さが2の冪乗で、角の座標は辺の長さの倍数となる。このうちの2点を決定すれば、その両方の点に囲まれた derived square ( 子要素の正方形 )も決まる。なお、この手法では x 要素と y 要素のビット群の相互配置性は shuffle ( 混ぜ合わせ )と呼ぶ。これらの特徴はより高次元に対しても拡張できる。
点群は実際にビットの相互配置をせずとも shuffle からソート可能である。先ず次元ごとに、2点の最上位ビットの排他的論理和を評価し、次に最上位ビットが最大の次元で shuffle の順位を決める。
排他的論理和は2点の座標が同一の場合最上位ビットをマスクする。shuffle は上位から下位へとビットを相互配置するので、最大の最上位ビットを持つ座標を識別でき、異なる shuffle 順位の最初のビットも識別でき、よって2点の座標を比較できる。 以下に Python のソースコードを示す: