Space-filling curves

A line that fills a square

In 1890, Giuseppe Peano shocked the mathematical world by constructing a continuous curve that passes through every point in a unit square. This was disturbing because it violated the intuition that a one-dimensional object should not be able to fill a two-dimensional space. David Hilbert followed in 1891 with a simpler construction, and dozens of variants have been discovered since.

The Hilbert curve

The Hilbert curve is constructed recursively. At iteration 1, it is a simple U-shape connecting four quadrants. At each subsequent iteration, each quadrant is subdivided into four smaller quadrants and connected with a smaller U-shape, with appropriate rotations and reflections to keep the path continuous. At iteration n, the curve visits 4ⁿ points arranged on a 2ⁿ × 2ⁿ grid. In the limit, it visits every point in the square.

The Peano curve

Peano’s curve divides the square into a 3 × 3 grid at each iteration instead of 2 × 2. It visits 9ⁿ points at iteration n on a 3ⁿ × 3ⁿ grid. The curve has a distinctive zigzag pattern with more complex self-similarity than the Hilbert curve.

Z-order (Morton) curve

The Z-order curve (also called the Morton curve or Lebesgue curve) is the simplest space-filling curve. It interleaves the bits of the x and y coordinates to produce a one-dimensional index. Geometrically, it traces a Z-shape through each group of four cells. While it does not preserve locality as well as the Hilbert curve (it has jumps), it is trivially computable from coordinates and is widely used in computer science.

The Dragon curve

The dragon curve is generated by a simple rule: start with a line segment, then repeatedly replace each segment with two segments at a right angle, alternating the direction of the turn. Unlike the Hilbert and Peano curves, the dragon curve is not strictly a space-filling curve in the mathematical sense — it does not fill a square — but it tiles the plane and has a Hausdorff dimension of 2, giving it the same fractal character.

Applications in computer science

Space-filling curves are not just mathematical curiosities. The Hilbert curve is used in database indexing (R-trees, spatial databases) because it preserves locality better than other orderings: points close in 2D tend to be close along the curve. The Z-order curve is used in texture mapping and memory layout for 2D arrays, improving cache performance. Both are used in parallel computing for load balancing: divide the Hilbert curve into equal segments and each processor gets a compact, contiguous region of space.

Dimension and measure

The existence of space-filling curves forced mathematicians to rethink what “dimension” means. A space-filling curve is a continuous surjection from [0,1] to [0,1]² — it maps every point in a line segment to every point in a square. This means the image of a one-dimensional set can have two-dimensional Lebesgue measure. The resolution came from topology: while the curve is surjective, it is not injective (it must cross itself), so the topological dimension of the line is still 1. The fractal (Hausdorff) dimension of the limit curve is 2.