Hilbert curve

The Hilbert curve is a continuous space-filling curve discovered by David Hilbert in 1891, two years after Giuseppe Peano's original construction. Where Peano's curve maps the unit interval onto the unit square through a nine-part subdivision, Hilbert's construction uses a four-part subdivision that produces superior locality preservation — the property that points close to each other in the one-dimensional parameter space remain close in the two-dimensional target space. This seemingly minor geometric distinction has made the Hilbert curve the dominant space-filling curve in computer science, despite the Morton Code's computational simplicity.

The Hilbert curve is not merely a mathematical curiosity. It is a coarse-graining operator — a systematic way of reducing dimension while preserving structure. In this respect it functions like the renormalization group in physics or the feature extractors in deep learning: it discards information that is irrelevant to a specific purpose (spatial locality) while preserving information that is relevant. The curve is a compression algorithm for topology.

Construction and Locality

The Hilbert curve is constructed recursively. At each iteration, the unit square is divided into four quadrants, and the curve visits each quadrant in a specific order (up, right, down, or variants) while maintaining continuity. The crucial property is that consecutive segments of the curve are always adjacent in space. This is not true for the Morton order, where the Z-shaped traversal creates discontinuities — points that are consecutive in the one-dimensional ordering can be far apart in space.

The locality preservation has a precise quantitative form. For two points at distance d in the two-dimensional space, their positions along the Hilbert curve are at most O(d²) apart. This quadratic bound is the best possible for any space-filling curve, and it explains why the Hilbert curve outperforms alternatives in cache-sensitive applications. When spatial data is stored in Hilbert order, nearby objects are likely to reside in the same cache line or disk block, reducing memory access costs by orders of magnitude.

Applications in Systems

The Hilbert curve's practical importance lies in its ability to solve a fundamental systems problem: how to store multi-dimensional data in one-dimensional memory without destroying spatial locality. This problem appears across domains:

In database indexing, the Hilbert curve is used in R-tree variants and spatial databases to map two-dimensional coordinates to a one-dimensional index key. The locality preservation guarantees that range queries — find