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.

Sources

${\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

ThatsMaths