Z-order Curve

Z-order Curve

In mathematical analysis and computer science, Z-order, Morton order, or Morton code is a function which maps multidimensional data to one dimension while preserving locality of the data points. It was introduced in 1966 by G. M. Morton. The z-value of a point in multidimensions is simply calculated by interleaving the binary representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used such as binary search trees, B-trees, skip lists or (with low significant bits truncated) hash tables. The resulting ordering can equivalently be described as the order one would get from a depth-first traversal of a quadtree; because of its close connection with quadtrees, the Z-ordering can be used to efficiently construct quadtrees and related higher dimensional data structures.

Read more about Z-order Curve:  Coordinate Values, Efficiently Building Quadtrees, Use With One-dimensional Data Structures For Range Searching, Related Structures, Applications in Linear Algebra

Famous quotes containing the word curve:

    In philosophical inquiry, the human spirit, imitating the movement of the stars, must follow a curve which brings it back to its point of departure. To conclude is to close a circle.
    Charles Baudelaire (1821–1867)