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:
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 14 August 2008.
HTML page formatted Fri Mar 25 16:20:35 2011.
Cite this as:
Paul E. Black, "space ordering method", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 August 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/spaceOrderingMethod.html