NIST

space ordering method

(algorithm)

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

See also point access method, spatial access method.

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:

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 Fri Feb 23 10:06:08 2018.

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: https://www.nist.gov/dads/HTML/spaceOrderingMethod.html