Hilbert's Space-Filling Curve, math that surprises you lesson

A pencil line, however long and wiggly, seems to leave most of a page blank. Hilbert’s construction draws a path through the four quarters of a square, then through sixteen smaller squares, then sixty-four, and so on, and every one of these drawings still covers no area at all. Yet the limit of the drawings is a continuous curve that passes through every single point of the square. This page builds the stages, uses nested squares to say exactly what the limit is, and explains why it reaches every point without being one-to-one.

Key terms

Hilbert curve

Definition Work in the unit square, the points $(x, y)$ with $0 \le x \le 1$ and $0 \le y \le 1$ . Stage $n$ of the construction cuts the square into a grid of $2^n$ by $2^n$ equal cells of side $2^{-n}$ and joins the centers of all $4^n$ cells, in a fixed order, by straight segments. Stage 1 visits the four quarters in the order lower left, upper left, upper right, lower right, which makes a U shape of three segments. Stage $n + 1$ is made of four copies of stage $n$ shrunk to half size, one in each quarter, visited in the same order as the quarters. The copies in the two upper quarters keep the orientation of stage $n$ . The copy in the lower-left quarter is flipped across that quarter’s diagonal from its lower-left corner to its upper-right corner, and the copy in the lower-right quarter is flipped across that quarter’s diagonal from its upper-left corner to its lower-right corner. These flips put the end of each copy in a cell next to the start of the following copy, so the copies join into one path. At every stage the path starts in the lower-left cell, ends in the lower-right cell, and each step goes between two cells that share a side. The stage $n$ path has $4^n - 1$ segments of length $2^{-n}$ , so its length is

\begin{aligned} L_n &= (4^n - 1) \cdot 2^{-n} \\[0.4em] &= 2^n - 2^{-n}. \end{aligned}

The Hilbert curve is not any one of these paths but their limit, a map $H$ that sends each time $t$ from 0 to 1 to a point $H(t)$ of the square, defined exactly in the card on nested squares. The surprise is that $H$ is continuous and reaches every point of the square. The resolution has two parts. No finite stage does this, since each stage is made of finitely many segments and covers zero area, and the limit map that does it is continuous and onto but not one-to-one. David Hilbert described the curve in 1891, a year after Giuseppe Peano published the first curve of this kind.

In plain words Each stage visits every cell of a finer grid, always moving to a neighbor, and inside every cell of one stage the next stage makes a small U through the four quarters of that cell. The curve is what these paths settle into when the refining goes on forever.

Example Stage 1 visits the centers $(\tfrac14, \tfrac14)$ , $(\tfrac14, \tfrac34)$ , $(\tfrac34, \tfrac34)$ and $(\tfrac34, \tfrac14)$ . Stage 2 begins in the lower-left quarter with a flipped U through $(\tfrac18, \tfrac18)$ , $(\tfrac38, \tfrac18)$ , $(\tfrac38, \tfrac38)$ and $(\tfrac18, \tfrac38)$ , steps up to $(\tfrac18, \tfrac58)$ in the upper-left quarter, and ends at $(\tfrac78, \tfrac18)$ after 16 centers. The counts grow quickly.

Stage	Cells visited	Segments	Length
$1$	$4$	$3$	$1.5$
$2$	$16$	$15$	$3.75$
$3$	$64$	$63$	$7.875$
$4$	$256$	$255$	$15.9375$

The length roughly doubles at each stage, while the area covered by the path stays 0.

Nested squares

Definition Number the $4^n$ cells of stage $n$ as $0, 1, \dots, 4^n - 1$ in the order the stage $n$ path visits them, and give cell $k$ the time interval from $k/4^n$ to $(k + 1)/4^n$ . Because stage $n + 1$ is built from copies of stage $n$ , the four smaller cells inside cell $k$ are visited one after another, and their time intervals are the four quarters of the interval of cell $k$ . Now write a time $t$ from 0 to 1 in base 4,

t = (0.d_1 d_2 d_3 \ldots)_4,

with each digit equal to 0, 1, 2 or 3. The digit $d_1$ picks one of the four quarters of the square, where 0, 1, 2 and 3 stand for the first, second, third and fourth quarter in the visiting order. Each later digit picks, in the same way, one of the four smaller cells inside the cell chosen so far. The chosen cells are nested squares, each inside the one before, with sides $\tfrac12$ , $\tfrac14$ , $\tfrac18$ and so on. Closed squares nested like this, with sides shrinking to 0, have exactly one point in common, and that point is $H(t)$ . The digits of $t$ are its address. A time such as $\tfrac14$ has two base 4 expansions, $(0.1000\ldots)_4$ and $(0.0333\ldots)_4$ , and both give the same point, because each copy of the curve ends at the corner where the next copy begins.

In plain words A time is an address that zooms in on the square one digit at a time. Each digit says which of four smaller cells to enter next, and the cells close in on a single point, the place where the curve is at that time.

Example Find the time at which the curve passes through $(\tfrac13, \tfrac13)$ . The point lies in the lower-left quarter, which is visited first, so $d_1 = 0$ and the time is between 0 and $\tfrac14$ . Inside that quarter the flipped U visits the lower-left, lower-right, upper-right and upper-left cells in that order, and the point lies in the upper-right one, which runs from $\tfrac14$ to $\tfrac12$ in both coordinates, so $d_2 = 2$ . That cell holds a copy of the whole curve shrunk to a quarter of the width and flipped across its diagonal on the line $y = x$ , and $(\tfrac13, \tfrac13)$ sits in the same relative position inside it as in the whole square, one third of the way across and one third of the way up. So the digits repeat, and

\begin{aligned} t &= (0.0202\ldots)_4 \\[0.4em] &= \frac{2}{16} + \frac{2}{16^2} + \cdots \\[0.4em] &= \frac{2}{15}. \end{aligned}

The nested squares have sides $\tfrac12, \tfrac14, \tfrac18, \dots$ and the matching time intervals run from 0 to $\tfrac14$ , from $\tfrac18$ to $\tfrac{3}{16}$ , from $\tfrac18$ to $\tfrac{9}{64}$ and so on, each containing $\tfrac{2}{15}$ . Since $\tfrac13$ is not a fraction with a power of 2 as its denominator, the point never lies on the edge of a cell. It belongs to exactly one cell at each stage, so $\tfrac{2}{15}$ is the only time at which the curve is there.

Continuous surjection

Definition A map $f$ from a set $A$ to a set $B$ is onto, or surjective, when every element of $B$ equals $f(a)$ for at least one $a$ in $A$ . It is one-to-one, or injective, when different elements of $A$ always have different images. A map from times to points is continuous when small changes in time give small changes in position. More precisely, for every distance $\varepsilon > 0$ there is a $\delta > 0$ such that any two times closer than $\delta$ are sent to points closer than $\varepsilon$ . A continuous surjection is a map that is both continuous and onto. The Hilbert curve is a continuous surjection from the interval $0 \le t \le 1$ onto the unit square. It is onto because every point of the square lies in a chain of nested cells, one at each stage, and the matching nested time intervals close in on a time $t$ whose image $H(t)$ is that point. It is continuous because two times that differ by at most $4^{-n}$ lie in one time interval of stage $n$ or in two consecutive ones, whose cells are equal or share a side. So the distance between their points satisfies

\lvert H(s) - H(t) \rvert \le \sqrt{5} \cdot 2^{-n},

the length of the diagonal of two cells side by side. It is not one-to-one, and no continuous map from the interval onto the square can be. A continuous one-to-one map from a closed interval onto a square would have a continuous inverse. Then removing the single point $H(\tfrac12)$ would split the square into two pieces, matching the two pieces of the interval on either side of $\tfrac12$ , but a square with one point removed is still in one piece.

In plain words The curve never jumps, since nearby times always give nearby points, and it misses nothing, since every point of the square is reached at some time. The price is uniqueness. Some points are reached at more than one time, so the square is not a stretched copy of the interval.

Example The center $(\tfrac12, \tfrac12)$ is where the copy in the upper-left quarter ends and the copy in the upper-right quarter begins, so $H(\tfrac12) = (\tfrac12, \tfrac12)$ . The times from 0 to $\tfrac14$ trace a shrunken, flipped copy of the whole curve, which reaches every point of the closed lower-left quarter, including its upper-right corner $(\tfrac12, \tfrac12)$ . So the center is reached again at some time before $\tfrac14$ , which turns out to be $t = \tfrac16$ , and the curve is not one-to-one. For continuity, times within $4^{-5} = \tfrac{1}{1024}$ of each other give points within $\sqrt{5}/32 \approx 0.070$ of each other.

Space-filling curve

Definition In this setting a curve is a continuous map from an interval of times, here $0 \le t \le 1$ , into the plane or into space, and the points it reaches form its image. A space-filling curve is a curve whose image contains a whole two-dimensional region, such as a square or a disk, or in space a solid region such as a ball. A path made of finitely many straight segments covers zero area, because each segment has zero area, so no finite stage of the construction is space-filling, however fine its grid. Drawing a fine stage with a thick pen can make it look solid, but a segment has no width, and the points it misses inside every cell are still missed. The Hilbert curve $H$ is space-filling, since its image is the whole unit square. Its times form a one-dimensional interval and its image is a two-dimensional square, so a continuous map can have an image of higher dimension than the set it starts from.

In plain words A space-filling curve is a single unbroken motion, from time 0 to time 1, that passes through every point of a solid region. No drawing can show one, because every drawing stops at a finite stage.

Example Each segment of stage $n$ joins the centers of two cells that share a side, so it lies on a vertical line $x = \tfrac{2j + 1}{2^{n+1}}$ or on a horizontal line $y = \tfrac{2j + 1}{2^{n+1}}$ for some whole number $j$ . The point $(\tfrac13, \tfrac13)$ has neither coordinate of this form, because $\tfrac13$ is not a fraction with a power of 2 as its denominator, so it lies on no finite stage at all. The center $(\tfrac12, \tfrac12)$ misses every stage too, since $\tfrac12 = \tfrac{2^n}{2^{n+1}}$ has an even numerator. Yet the limit reaches both points, with $H(\tfrac{2}{15}) = (\tfrac13, \tfrac13)$ and $H(\tfrac12) = (\tfrac12, \tfrac12)$ . The same holds for every point neither of whose coordinates is a fraction with a power of 2 as its denominator.

Check yourself

How many cells does the stage 6 path visit, how many segments does it have, and how long is it? At which stage is the path first longer than 100?

Show the answer

Stage 6 visits $4^6 = 4096$ cells with $4095$ segments of length $\tfrac{1}{64}$ , so its length is

\frac{4095}{64} = 63.984375,

which agrees with $2^6 - 2^{-6}$ . The length $2^n - 2^{-n}$ is less than $2^n$ , so stage 6 is below 100, and stage 7 has length $2^7 - 2^{-7} \approx 127.99$ . The path is first longer than 100 at stage 7. Its area is still 0, however long it gets.

Use the address of $t = \tfrac13$ to find $H(\tfrac13)$ . Is it the point one third of the way along the stage 1 path?

Show the answer

Since $\tfrac13 = \tfrac14 + \tfrac{1}{16} + \tfrac{1}{64} + \cdots$ , its base 4 expansion is $(0.111\ldots)_4$ . The first digit 1 picks the upper-left quarter, the second one visited. The copy of the curve in that quarter has the same orientation as the whole, so the next digit 1 picks the upper-left quarter of that quarter, and so on. The nested squares are the squares of side $\tfrac12, \tfrac14, \tfrac18, \dots$ in the upper-left corner of the unit square, and the only point in all of them is the corner $(0, 1)$ . So $H(\tfrac13) = (0, 1)$ .

The stage 1 path has length $\tfrac32$ , and one third of that length takes it from $(\tfrac14, \tfrac14)$ straight up to $(\tfrac14, \tfrac34)$ , the center of the upper-left cell. Both points lie in the upper-left quarter, but they are different points. The time $t$ is not the distance along a drawn stage. It gives every cell of a stage the same share of time, and the point is fixed only by all the digits together.

The center $(\tfrac12, \tfrac12)$ is reached at the times $\tfrac16$ and $\tfrac12$ . Use the lower-right quarter and the answer to question 2 to find a third time.

Show the answer

The times from $\tfrac34$ to 1 trace the whole curve shrunk to half size and flipped across the lower-right quarter’s diagonal from its upper-left to its lower-right corner. In coordinates, the time $\tfrac34 + \tfrac{s}{4}$ is sent to the image of the point $H(s) = (x, y)$ under this flip, the point $(x', y')$ with

\begin{aligned} x' &= 1 - \tfrac{y}{2}, \\[0.4em] y' &= \tfrac{1}{2} - \tfrac{x}{2}. \end{aligned}

Take $s = \tfrac13$ , where $H(\tfrac13) = (0, 1)$ . The time is $\tfrac34 + \tfrac{1}{12} = \tfrac56$ , with address $(0.3111\ldots)_4$ , and the point is $(1 - \tfrac12, \tfrac12 - 0) = (\tfrac12, \tfrac12)$ . So $H(\tfrac56) = (\tfrac12, \tfrac12)$ .

These three times are the only ones. The center lies in all four quarters, the copy of the curve in each quarter passes through it at a single time, and the copies in the two upper quarters share the time $\tfrac12$ . Three different times give one point, a concrete case of a continuous surjection that is not one-to-one.