Space-Filling Curves, Part I: “I see it, but I don’t believe it”

We are all familiar with the concept of dimension: a point is zero-dimensional, a line is one-dimensional, a plane is two-dimensional and the space around us is three-dimensional. A position on a line can be specified by a single number, such as the distance from a fixed origin. In the plane, a point can be located by giving its Cartesian coordinates {(x,y)}, or its polar coordinates {(\rho,\theta)}. In space, we may specify the location by giving three numbers {(x,y,z)}.

In 1872, Georg Cantor made a remarkable discovery. He found a one-to-one mapping {f : \mathit{I} \rightarrow \mathit{Q}} between the one-dimensional unit interval {\mathit{I} := [0,1]} and the two-dimensional unit square {\mathit{Q} := [0,1]\times[0,1]}. His idea is easily explained: any point {t} on the unit interval {\mathit{I}} may be expressed in decimal form, {t = 0.d_1 d_2 d_3 \dots }. We use the odd and even digits of {t} to construct two numbers

\displaystyle x = 0.d_1 d_3 d_5 \dots \qquad \mbox{and} \qquad y = 0.d_2 d_4 d_6 \dots \,,

giving us a point {(x,y)} in the unit square {\mathit{Q}}. Any point in {Q} can be obtained from some {t\in I}.

It is clear that this argument can be reversed: given the two coordinates of any point in {Q},

\displaystyle x = 0.abcd\dots \qquad\mbox{and}\qquad y = 0.\alpha\beta\gamma\delta\dots

we can form the number {t = 0.a\alpha b\beta c\gamma d\delta \dots} in the interval {I}, thereby mapping {Q} into {I} (there are some “sticky points” that have been ignored in this article. For more detail, see Gouvêa, 2011). In a letter to Dedekind in 1877, Cantor wrote of the result “I can only say: je le vois, mais je ne le crois pas”. The letter was in German, but the famous phrase “I see it, but I don’t believe it” was in French.

Cantor’s result was remarkable: it meant that a point in the two-dimensional unit square could be indicated by a single number in {I}. Indeed, this was also true for a point in {I^k} for any {k\in\mathbb{N}}. So, there were far-reaching consequences for the concept of dimensionality.

In 1878, Cantor proved that any two smooth manifolds of any finite dimensions have the same cardinality. But could there be a continuous mapping between them? In particular, could there be a one-to-one continuous function from {I} to {Q}? The answer is no, as was proved by Eugen Netto in 1879.

Dropping the requirement of the mapping being one-to-one, mathematicians sought a continuous surjective mapping {f: I \rightarrow Q}. The first to find one was Giuseppe Peano. The following year, 1891, the great David Hilbert found a simpler map and provided a clear description of its construction and its properties.

The Hilbert Curve

Top from left: {H_1}. Four quadrants. Reflection diagonals. Bottom from left: four scaled copies of {H_1} before reflection. After reflection. Linking gives {H_2}.

The Hilbert curve can be constructed as the limit of a sequence of functions of increasing detail. The zero-order map is constant: {H_0(t) = (\frac{1}{2},\frac{1}{2})}. We move from {H_n} to {H_{n+1}} by a recursive process: four copies of {H_n} are scaled by {\frac{1}{2}} and mapped to the four quadrants {Q_0}, {Q_1}, {Q_2} and {Q_3} of the square (see Figure above). They are arranged in such a way that the end of each one lines up with the beginning of the following one. This requires us to reflect the curves in the south-west and south-east quadrants about the diagonals through the centre of {Q}. Finally, connecting line-segments are added to link the four quadrants in a single curve. The first six approximations are shown in the Figure below.

Approximations of order 1 to 6 for the Hilbert curve.

The approximating curves give an impression of the Hilbert curve, which we may denote by {H_\infty} or just {H}. However, it is far from clear how to calculate any particular value {H(t)}. It is also far from obvious that the mapping is surjective. Does this curve really pass through every point in the unit square. We will return to these questions in Part II.


{\bullet} Gouvêa, Fernando Q., 2011: Was Cantor Surprised? Amer. Math. Monthly, 118.

{\bullet} Sagan, Hans, 1994: Space-filling curves. Springer-Verlag, New York. 193pp. ISBN: 0-387-94265-3.

  *     *     *

New Collection recently Published

GREATLY REDUCED PRICE   from   Logic Press.

Now available also in hardback form 

Last 50 Posts