Z-order curve
[3] The z-value of a point in multidimensions is simply calculated by bit interleaving the binary representations of its coordinate values.
[4] Once the data are sorted by bit interleaving, any one-dimensional data structure can be used, such as simple one dimensional arrays, binary search trees, B-trees, skip lists or (with low significant bits truncated) hash tables.
The figure below shows the Z-values for the two dimensional case with integer coordinates 0 ≤ x ≤ 7, 0 ≤ y ≤ 7 (shown both in decimal and binary).
The interleaving of bits from the x and y components of each point is called the shuffle of x and y, and can be extended to higher dimensions.
The dimension for which the most significant bit is largest is then used to compare the two points to determine their shuffle order.
[8] This is shown in the following Python code: One way to determine whether the most significant bit is smaller is to compare the floor of the base-2 logarithm of each point.
For each adjacent pair of points, the derived square is computed and its side length determined.
The result of this is a compressed quadtree, where only nodes containing input points or two or more children are present.
Rather than building a pointer based quadtree, the points can be maintained in sorted order in a data structure such as a binary search tree.
Searching in decreasing direction is analogous with LITMAX which is the highest Z-value in the query range lower than F. The BIGMIN problem has first been stated and its solution shown in Tropf and Herzog.
Applying the method hierarchically (according to the data structure at hand), optionally in both increasing and decreasing direction, yields highly efficient multidimensional range search which is important in both commercial and technical applications, e.g. as a procedure underlying nearest neighbour searches.
[15] As long ago as 1966, G.M.Morton proposed Z-order for file sequencing of a static two dimensional geographical database.
Arranging the matrix elements in Z-order then improves locality, and has the additional advantage (compared to row- or column-major ordering) that the subroutine for multiplying two blocks does not need to know the total size of the matrix, but only the size of the blocks and their location in memory.
[17] Buluç et al. present a sparse matrix data structure that Z-orders its non-zero elements to enable parallel matrix-vector multiplication.
This is important because 3D rendering involves arbitrary transformations (rotations, scaling, perspective, and distortion by animated surfaces).
Storing the data as a pointer-based tree requires many sequential pointer dereferences to iterate over the octree in depth-first order (expensive on a distributed-memory machine).
