Space-filling

Hilbert curve

David Hilbert introduced this space-filling curve in 1891, a year after Peano’s original construction. The Hilbert curve has a cleaner recursive geometry and excellent locality preservation, making it the canonical example in modern computer science.

At a glance

Construction

Take a U-shape connecting four cells of a 2 × 2 grid. To refine, replace each cell with a 2 × 2 sub-grid and connect them with rotated U-shapes so the result is still a single Jordan curve. Iterate. The limit maps [0, 1] continuously onto [0, 1] × [0, 1].

Locality preservation

For two points in [0, 1] at distance t, their Hilbert-curve images are at most C √t apart in the plane. This is the best possible scaling for any space-filling curve and gives Hilbert ordering its practical edge over row-major traversal: nearby parameters map to nearby points.

Applications

• Database indexing: spatial keys for 2D / 3D queries.
• Image processing: cache-friendly traversal of pixel grids.
• Network design: load balancing across geographic regions.
• Visualisation: mapping linear genomic data onto 2D heatmaps.

References

• Hilbert, D., “Ueber die stetige Abbildung einer Linie auf ein Flächenstück,” Math. Ann., 1891.
• Sagan, H., Space-Filling Curves, Springer, 1994.
• Peano curve · L-systems

Try it

Run an interactive playground at /tools/lsystems.