Peano curve (1890) the first example of a space-filling curve to be discovered.

Hilbert curve (1891) gives a mapping between 1D and 2D space that fairly well preserves locality.[3] If (x,y) are the coordinates of a point within the unit square, and d is the distance along the curve when it reaches that point, then points that have nearby d values will also have nearby (x,y) values. The converse can’t always be true. There will sometimes be points where the (x,y) coordinates are close but their d values are far apart.

Z-order curve (1966). 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.

As an alternative, the Hilbert curve has been suggested as it has a better order-preserving behaviour, but here the calculations are much more complicated, leading to significant processor overhead.

Paper multidimensional range search

More detailed explaination on narrowing range search:

• How to use Morton Order(z order curve) in range search?
• LitMax and BigMin computation

• HN - An interesting variant of space-filling curves + dimensionality reduction is [Geohash](https://en.wikipedia.org/wiki/Geohash] [^:1](http://geohash.org/) which takes a lon/lat and uses a Z-curve approach to produce a hash such as u4pruydqqvj representing the location.

see also

• Hilbert’s Curve: Is infinite math useful? (3blue1Brown)
• Experiment with Penrose Tilings and other patterns / Pattern Collider
• Google’s S2, geometry on the sphere, cells and Hilbert curve