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
| Designer | David Hilbert, 1891 |
|---|---|
| Hausdorff dimension | 2 (space-filling) |
| Topological dimension | 1 at each finite step |
| L-system | Axiom A; A → +BF−AFA−FB+, B → −AF+BFB+FA− |
| Angle | 90° |
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.