The Hilbert Curve: A Line That Fills a Square

What a space-filling curve is — and why it sounds impossible

A curve, formally, is a continuous map h from an interval (say [0,1]) into a space. A space-filling curve is a curve whose image is the whole of a two-dimensional region: a continuous surjection h : [0,1] → [0,1]² whose picture is the entire solid unit square. The word 'continuous' is the whole difficulty. Georg Cantor had shown in 1877 that [0,1] and [0,1]² have the same cardinality — there is a bijection between the points of a line and the points of a square — but his bijection was violently discontinuous, shuffling nearby points to opposite ends. The open question, posed by Cantor to Dedekind, was whether the correspondence could be made continuous.

Giuseppe Peano answered yes in 1890 with the first space-filling curve, defined analytically through base-3 digit manipulations. A year later Hilbert gave the version everyone draws: a purely geometric, recursive construction that you can watch converge. Both are continuous surjections of an interval onto a square.

One thing such a curve can never be is a continuous bijection. This is Netto's theorem (1879): there is no continuous bijection between [0,1] and [0,1]². The reason is topological — a continuous bijection from a compact space is a homeomorphism, but the interval and the square are not homeomorphic (delete an interior point and the interval falls into two pieces, while the square stays connected). So a space-filling curve must revisit points: it is onto but not one-to-one. Continuity and surjectivity are compatible; adding injectivity is not.

Hilbert's recursive construction, step by step

Hilbert's idea is to build a correspondence between subintervals of the line and subsquares of the square, refined level by level, so that adjacent pieces always map to adjacent pieces.

• Level 1. Cut the square into four quadrants and cut [0,1] into four equal subintervals. Order the quadrants so the path enters one, steps to an edge-neighbor, then another, then the last — the classic U-shape (or 'staple'). The four subintervals map, in order, onto these four quadrants.
• Recurse. Inside each quadrant, place a half-size copy of the whole U-pattern, but rotated and reflected so that the exit of one quadrant's copy lines up with the entrance of the next. Two of the four copies are reflected across a diagonal; that twist is what keeps the pen moving to an edge-adjacent cell at every seam.
• Level n. Repeating n times partitions the square into a 2ⁿ × 2ⁿ grid of 4ⁿ cells, each of side 2⁻ⁿ, and partitions [0,1] into 4ⁿ subintervals of length 4⁻ⁿ. The polygonal curve Hₙ threads through all 4ⁿ cell centers in order.

The same recipe can be written as an L-system (turtle graphics): with F = draw forward, + = turn left 90°, − = turn right 90°, use rules A → −BF+AFA+FB− and B → +AF−BFB−FA+ starting from A. Expanding the rules n times and drawing F strokes traces Hₙ exactly. Equivalently, one can compute the map arithmetically: read the parameter t in base 4; each base-4 digit selects a quadrant, and a running rotation/reflection (the orientation inherited from the digits so far) fixes where that quadrant sits. This bit-twiddling version converts a 1-D index to (x, y) in O(n) operations and is what real software uses.

Why the limit exists and is continuous

The finished Hilbert curve is the limit h = limₙ Hₙ of the polygonal approximations. That this limit exists, and is continuous, is the crux — and it follows from uniform convergence.

Parametrize every Hₙ on the same interval [0,1]. During the subinterval assigned to a given level-n cell, both Hₙ and every later Hₘ (m ≥ n) stay inside that one cell, because refinement only subdivides within cells and never leaves them. A cell has side 2⁻ⁿ, so its diameter is 2⁻ⁿ√2, and therefore

• ‖Hₘ − Hₙ‖∞ ≤ 2⁻ⁿ√2 for all m ≥ n.

The tail 2⁻ⁿ√2 → 0, so the sequence (Hₙ) is uniformly Cauchy in the complete space of continuous maps [0,1] → ℝ² with the sup norm. Hence it converges uniformly to a limit h, and a uniform limit of continuous functions is continuous. So h is a genuine continuous curve.

It is also surjective. Take any point p in the square. For every n, p lies in some level-n cell, and Hₙ passes through that cell, so the curve comes within 2⁻ⁿ√2 of p. The image of h is the continuous image of the compact set [0,1], hence compact, hence closed; a closed set that p is arbitrarily close to must contain p. Therefore h hits every point of the square — the line truly fills the plane region.

Dimension, length, and the paradox resolved

The curve looks one-dimensional — you draw it with one moving point — yet its image is the full square. So what is its dimension? The answer is 2, in every sensible sense: the image is the unit square, which has topological dimension 2, Hausdorff dimension 2, and Lebesgue measure (area) exactly 1. This is the headline: a continuous curve can have a two-dimensional image. Space-filling curves are the standard proof that topological dimension is not preserved by continuous maps — only by homeomorphisms.

The length tells the same story from the other side. The level-n approximation joins 4ⁿ cell centers by 4ⁿ − 1 segments, each of length 2⁻ⁿ (consecutive cells are edge-adjacent), so its length is

• Lₙ = (4ⁿ − 1)·2⁻ⁿ = 2ⁿ − 2⁻ⁿ,

which runs 1.5, 3.75, 7.875, 15.9375, … and diverges. The limiting curve has infinite length and is nowhere differentiable — at no parameter does it have a tangent direction.

How fast can it move? A subinterval of length 4⁻ᵏ maps into (at most two edge-adjacent) cells of side 2⁻ᵏ, a block of diameter ≤ 2⁻ᵏ√5. Choosing k so that 4⁻⁽ᵏ⁺¹⁾ < |s − t| ≤ 4⁻ᵏ gives the Hölder-½ bound |h(s) − h(t)| ≤ 2√5·|s − t|^{1/2}. The exponent ½ is optimal and is forced by dimension: an interval of length δ must cover area ≈ δ, and a region of area δ has diameter ≈ √δ. No space-filling curve can be Lipschitz (exponent 1) — that would keep length finite, contradicting a two-dimensional image. Finally, because injectivity is impossible, some points are revisited; the multiple points all lie on the dyadic grid lines, a set of area zero, and each point is hit only finitely many times.

Locality: why close on the line means close in the plane

The Hölder-½ inequality is not just a curiosity — it is the locality guarantee that makes the Hilbert curve useful. It says the map cannot make big jumps: move a little in the parameter t and you move only a little (≤ 2√5·√Δt) in the plane. Equivalently, a short run of the curve stays in a small patch of the square.

Contrast the naive alternative. A row-major raster scan (read left-to-right, top-to-bottom) has terrible locality: two pixels in the same column but adjacent rows are one step apart in the plane yet a whole row-width apart in the ordering, and every row wrap is a long jump back across the image. A Z-order (Morton) curve is better but still leaps across quadrant seams. The Hilbert curve never jumps at all — every consecutive step is to an edge-adjacent cell — and among all known orderings it minimizes how badly plane-neighbors get separated.

The practical measure is clustering: cover a query rectangle and count how many contiguous runs of the curve you need. Fewer runs means fewer disk seeks or cache misses. Empirically and by the bounds of Moon and colleagues (2001), the Hilbert curve produces the fewest clusters of the common orderings — a rectangle of area A typically needs O(√A) runs rather than O(A). That is the whole reason it shows up in Hilbert R-trees and other spatial indexes, in image compression and dithering, in cache-oblivious matrix layouts, and in the well-known xkcd 'map of the internet' that lays IP address space along a Hilbert curve so that numerically nearby addresses land in nearby regions.

History, cousins, and where it goes next

History. Cantor's 1877 line-to-square bijection created the puzzle; Netto's 1879 theorem showed a continuous bijection was impossible; Peano's 1890 construction gave the first continuous surjection, defined by base-3 digit rules; and Hilbert's 1891 paper recast it as the geometric limit of nested U-shapes, complete with the picture that made the idea intuitive. Hilbert's contribution was clarity: an explicitly self-similar, drawable process that visibly converges.

Cousins. The Hilbert curve has many relatives. The Moore curve is a closed-loop variant (it returns to its start). The Peano curve subdivides into 3 × 3 = 9 pieces instead of 2 × 2 = 4. Sierpiński, Lebesgue (built on the Cantor set), and Osgood curves are other space-fillers, some with positive-area but non-self-intersecting behavior. The same construction generalizes to three and higher dimensions: a 3-D Hilbert curve threads a cube through 8ⁿ subcubes and is Hölder-⅓, and in general a d-dimensional version is Hölder-1/d.

Open threads. Space-filling curves remain an active engineering tool: choosing the ordering that best clusters real query workloads, deriving sharp locality constants (the exact best Hölder constant and the exact worst-case clustering ratio are still refined), and building fast index-to-coordinate hardware. The pure-math lesson is permanent, though — dimension, length, and cardinality are three different notions of 'size,' and the Hilbert curve is the cleanest place to watch them come apart: a single continuous line, of infinite length, filling a square of area 1.

How different orderings of a 2ⁿ × 2ⁿ grid trade off simplicity against locality

Scan order	Consecutive step	Locality of a query box	Long jumps?
Row-major raster	Unit within a row, then jump a full row	Poor — neighbors split across rows	Yes — one per row wrap
Boustrophedon (snake)	Always to an adjacent cell	Moderate — good along rows only	No, but 1-D-style locality
Z-order / Morton	1 cell up to a full quadrant width	Good — but breaks at quadrant seams	Yes — at each seam
Hilbert curve	Always to an edge-adjacent cell	Best known — few clusters per box	No jumps at all