space ordering method

(algorithm)

Definition: A mapping from a discrete k-dimensional space into a linear order.

Note: A concrete version of the problem is, in what order should one visit every square in a checkerboard? Equivalently, how should one map a 2-dimensional array in memory?

A transversal of the mapped points in their linear order yields a space-filling curve.

There is a good survey on pages 167-169 of
Hanan Samet, Object-Based and Image-Based Object Representation, ACM Computing Surveys, 36(2):159-217, June 2004. The article describes several methods and reviews their properties:

row order (row major)
row-prime order
Morton order
Peano-Hilbert order
Cantor-diagonal order
spiral order
Gray order
double Gray order
U order

Author: PEB

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 14 August 2008.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "space ordering method", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 August 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/spaceOrderingMethod.html