Why does the Hilbert curve fill the whole square?

Question

I have never seen a formal definition of the Hilbert curve, much less a careful analysis of why it fills the whole square. The Wikipedia and Mathworld articles are typically handwavy.

I suppose the idea is something like this: one defines a sequence of functions $f_i(t) : [0,1]\to {\Bbb R}^2$, and then considers the pointwise limit $f(t) = \lim_{i\to\infty} f_i(t)$.

But looking at the diagram, it is not clear that the sequence converges. I can imagine that we might think of following a single point in the range of $f_i$ as $i$ increases, and that point might move around, but only by $2^{-i}$ at each stage as we pass from $f_i$ to $f_{i+1}$, and so eventually approaches a limiting position. But I don't know how we'd get from there to showing that $f_i(t)$ converges for a particular value of the argument, especially for an argument other than a dyadic rational.

And even if it does converge, every point in the range of each $f_i$ has at least one rational coordinate, so it is not at all clear why a point like $({1\over\sqrt2}, {1\over\sqrt2})$ should be in the range of $f$.

If there is an easy explanation, I would be glad to hear it, but I would also be glad to get a reference in English.

Answer 1

Looking at the pictures, the partial curves are obtained by joining the centres of smaller squares within the square. In the first step one divides the unit square into 4 squares of side $1/2$. Then each of these squares is divided again into $4$ squares, and so on. So the whole thing is reduced to the numbering of the successive subdivisions of the square: $f_n$ will be the curve obtained by joining the centres of the $4^n$ squares of side $2^{-n}$ according to the proper numbering scheme.

One can make the convention that $f_n:[0,1]\to[0,1]^2$, and we represent the part of the line corresponding to the $k^{\rm th}$ square using the interval $[(k-1)4^{-n},k\,4^{-n})$.

The numbering for the first $4$ squares (with sides $1/2$) is $1,2,3,4$ where $1$ is the lower left and then we proceed clockwise.

Given then $n^{\rm th}$ ordering, we obtain the $(n+1)^{\rm th}$ ordering in the following way: the $4^{n+1}$ squares are grouped in four main groups of $4^{n}$ squares corresponding to the four "quadrants" of the unit square ("first" quadrant is lower left, "second" quadrant is upper left, "third" quadrant is upper right, "fourth" quadrant is lower right). In each quadrant we will use the numbering from the $n^{\rm th}$ numbering, in the following way:

First quadrant: we take the $n^{\rm th}$ numbering, rotate it $90$ degrees clockwise and use reverse order.

Second quadrant: we take the $n^{\rm th}$ numbering in its original order (of course, replacing $1$ with $4^n+1$, $2$ with $4^n+2$, etc.

Third quadrant: we take the $n^{\rm th}$ numbering in its original order (of course, replacing $1$ with $2\times4^n+1$, $2$ with $2\times4^n+2$, etc.

Fourth quadrant: we take the $n^{\rm th}$ numbering, rotate it $90$ degrees counter-clockwise and use reverse order, starting with $3\times4^n+1$.

(this is not that easy to write or read, but it is very easy to check if you draw the squares)

The two claims to be proven are:

1) the sequence $\{f_n\}$ converges uniformly;

2) the limit function touches every point in the square.

To prove 1), we note that in the interval $[k4^{-n},(k+1)4^{-n})$, both $f_n$ and $f_{n+1}$ take values in the same square of side $2^{-n}$. This shows that $$ |f_{n+1}-f_n|\leq2^{-n}\ \ \ \text{ uniformly.} $$

Regarding 2), if we write $f=\lim f_n$, then $f$ is continuous, and so the image of the compact interval $[0,1]$ is compact, so in particular it is closed. Fix any point $(x,y)\in[0,1]^2$. Fix $n$; then there exists a square from our grid, of side $2^{-n}$ that contains $(x,y)$; say it's the $k^{\rm th}$ one. Then $$ \|f_n(k/4^n)-(x,y)\|\leq 2^{-n}. $$ Since $f=f_n+\sum_{m=n}^\infty (f_{m+1}-f_m)$, $$ \|f(k/4^n)-(x,y)\|\leq\|f_n(k/4^n)-(x,y)\|+\sum_{m=n}^\infty\|f_{m+1}-f_m\|\\ \leq2^{-n}+\sum_{m=n}^\infty2^{-m}=2^{-n}+2^{-n+1}=\frac3{2^{n}}. $$ This shows that $(x,y)$ is in the closure of the graph of $f$, but we already know that the graph of $f$ is closed, and so the image of $f$ is $[0,1]^2$.

Answer 2

Since no one has yet given you any references in English, below are a couple of books that are fairly complete for what you want.

Each book is pitched at the U.S. advanced undergraduate level. Sagan's book is very detailed with historical issues for these curves and it is also quite readable. The book by Darst seems decent also (it has much less on history), but I haven't looked at it much yet (despite having gotten a copy about two years ago; I've had Sagan's book since around 1995).

Curious Curves by Darst/Palagallo/Price (2009)

http://www.amazon.com/dp/9814291285

Space-Filling Curves by Sagan (1994)

http://www.amazon.com/dp/0387942653

Answer 3

I really like the answer of Martin Argerami. The only point that worried me was

(this is not that easy to write or read, but it is very easy to check if you draw the squares)

To circumvent this problem, one can use the following argument that is based on Banach's fixed point theorem (note that the geometric idea is still the same as for the construction of the Hilbert curve and/or in the post of Martin Argerami). Also compare the following to the post of john mangual.

We define mappings

$$ \begin{eqnarray*} A_{1}: & \left[0,1\right]^{2}\rightarrow\left[0,\frac{1}{2}\right]^{2}\subset\left[0,1\right]^{2}, & x\mapsto\frac{1}{2}\left[\left(\begin{array}{cc} 0 & 1\\ -1 & 0 \end{array}\right)\left(x-\left(\begin{matrix}1/2\\ 1/2 \end{matrix}\right)\right)+\left(\begin{matrix}1/2\\ 1/2 \end{matrix}\right)\right]\\ & & \phantom{x}=\frac{1}{2}\left(\begin{array}{cc} 0 & 1\\ -1 & 0 \end{array}\right)\,x+\left(\begin{matrix}0\\ 1 \end{matrix}\right),\\ A_{2}: & \left[0,1\right]^{2}\rightarrow\left[0,\frac{1}{2}\right]\times\left[\frac{1}{2},1\right]\subset\left[0,1\right]^{2}, & x\mapsto\frac{1}{2}x+\left(\begin{matrix}0\\ 1/2 \end{matrix}\right),\\ A_{3}: & \left[0,1\right]^{2}\rightarrow\left[\frac{1}{2},1\right]^{2}\subset\left[0,1\right]^{2}, & x\mapsto\frac{1}{2}x+\left(\begin{matrix}1/2\\ 1/2 \end{matrix}\right),\\ A_{4}: & \left[0,1\right]^{2}\rightarrow\left[\frac{1}{2},1\right]\times\left[0,\frac{1}{2}\right]\subset\left[0,1\right]^{2}, & x\mapsto\frac{1}{2}\left[\left(\begin{array}{cc} 0 & -1\\ 1 & 0 \end{array}\right)\left(x-\left(\begin{matrix}1/2\\ 1/2 \end{matrix}\right)\right)+\left(\begin{matrix}1/2\\ 1/2 \end{matrix}\right)\right]+\left(\begin{matrix}1/2\\ 0 \end{matrix}\right)\\ & & \phantom{x}=\frac{1}{2}\left(\begin{array}{cc} 0 & -1\\ 1 & 0 \end{array}\right)x+\left(\begin{matrix}1\\ 0 \end{matrix}\right). \end{eqnarray*} $$

These are just the rotations (+scaling and shifting) that are used in the numbering as in the post of Martin Argerami.

It is easy to check that these are well-defined and surjective maps (even bijective) that satisfy

$$\tag {*} \begin{equation} \left\Vert A_{j}x-A_{j}y\right\Vert _{2}=\frac{1}{2}\cdot\left\Vert x-y\right\Vert _{2} \end{equation} $$

for all $j=1,\dots,4$ and $x,y \in [0,1]^2$.

For $j=1,\dots,4$ we also set $I_{j}:=\left[\frac{j-1}{4},\frac{j}{4}\right]\subset\left[0,1\right]^{2}$ and $$ \begin{eqnarray*} \varphi_{1}: & I_{1}\rightarrow\left[0,1\right], & x\mapsto1-4x,\\ \varphi_{2}: & I_{2}\rightarrow\left[0,1\right], & x\mapsto4\cdot\left(x-\frac{1}{4}\right),\\ \varphi_{3}: & I_{3}\rightarrow\left[0,1\right], & x\mapsto4\cdot\left(x-\frac{1}{2}\right),\\ \varphi_{4}: & I_{4}\rightarrow\left[0,1\right], & x\mapsto1-4\cdot\left(x-\frac{3}{4}\right). \end{eqnarray*} $$

It is again an easy exercise to show that these are well-defined and surjective (even bijective).

Now, let $$ M:=\left\{ f\in C\left(\left[0,1\right];\mathbb{R}^{2}\right) \,\middle|\,f\left(0\right)=\left(\begin{matrix}0\\ 0 \end{matrix}\right),\; f\left(1\right)=\left(\begin{matrix}1\\ 0 \end{matrix}\right)\;,f\left(\left[0,1\right]\right)\subset\left[0,1\right]^{2}\right\} . $$

It is easy to see that this is a closed, nonempty subset of $C([0,1]; \Bbb{R}^2)$, when this space is equipped with the $\sup$-norm (let us use $|\cdot| = \Vert \cdot \Vert_2$ on $\Bbb{R}^2$).

We now define an operator $T : M \rightarrow M$ by

$$ \left(Tf\right)\left(x\right):=A_{j}\left(f\left(\varphi_{j}\left(x\right)\right)\right)\text{ for }x\in I_{j}\text{ and }j\in\{1,2,3,4\} $$

One can check that $Tf$ is a well-defined, continuous function for $f \in M$ and even $Tf \in M$ for $f \in M$, so that $T$ is well-defined.

Using the estimate $(\ast)$ above, one easily gets

$$ \left\Vert Tf-Tg\right\Vert _{\sup}\leq\frac{1}{2}\cdot\left\Vert f-g\right\Vert _{\sup} $$

for all $f,g \in M$. Thus, by Banach's fixed point theorem, there is a (unique) fixed point $f_0 \in M$ of $T$, which is thus a continuous map $f_0 : [0,1] \rightarrow [0,1]^2$. It remains to show that $f_0$ is surjective. As the image $f_0 ([0,1])$ is compact, it suffices to show that it is dense in $[0,1]^2$.

Using induction on $j \in \Bbb{N}_0$, we will show that for each $y \in [0,1]^2$, there is some $x \in [0,1]$ satisfying

$$\tag {**} \left\Vert f_{0}\left(x\right)-y\right\Vert _{2}\leq\sqrt{2}\cdot2^{-j}. $$

This is clear for $j=0$, as the diameter of $[0,1]^2$ is just $\sqrt{2}$.

For the induction step, note that there is some $j \in \{1, \dots, 4\}$ such that $y \in A_j ([0,1]^2)$, i.e. $y = A_j y'$ for some $y' \in [0,1]^2$. By induction, there is some $x' \in [0,1]$ such that $(\ast \ast)$ is satisfied for $x'$ and $y'$ instead of $x,y$.

Furthermore (because $\varphi_j$ is surjective), there is $x \in I_j$ with $x' = \varphi_j (x)$.

Now, the fixed point property $f_0 =Tf_0$ implies

$$ f_{0}\left(x\right)=\left(Tf_{0}\right)\left(x\right)=A_{j}\left(f_{0}\left(\varphi_{j}\left(x\right)\right)\right)=A_{j}\left(f_{0}\left(x'\right)\right), $$

Using the estimate $(\ast)$, we arrive at

\begin{align} \left\Vert f_{0}\left(x\right)-y\right\Vert _{2}&=\left\Vert A_{j}\left(f_{0}\left(x'\right)\right)-A_{j}y'\right\Vert _{2}=\frac{1}{2}\cdot\left\Vert f_{0}\left(x'\right)-y'\right\Vert _{2}\\ &\leq\frac{1}{2}\cdot\sqrt{2}\cdot2^{-j}=\sqrt{2}\cdot2^{-\left(j+1\right)}, \end{align} which completes the proof.

Answer 4

I had also similar doubts when I first learnt about the Hilbert curve. The way I see it - informally:

Assume $x$ is a point inside the square with irrational coordinates. Does the limit curve really includes that point? Yes. Does this means that there must be some curve $f_n$ (for some "big enough" $n$) that touches it? No, of course, there isn't.

You have the right intuition, in that we have a succession of mappings $f_i(t):[0,1] \to \mathbb{R}^2$ and we are interested in its limit. We can think the parameter as a "time", and in each iteration we increment the "velocity" so as to follow the full curve in the same time.

What we want to see is that we indeed can find a $t_x \in [0,1]$ such that $f(t_x)=x$, i.e., that there an instant of time can be found, so that in the limit the curve passes over our point $x$ at that time.

Now, for each iteration $k$ divide the square in $2^k \times 2^k $ squares. The curve visits the center of these squares at time instants $i/4^k$ ($i=1.. 4^k$) (unimportant border effect: assume that we start in the first point at time $1/4^k$ instead of time $0$). Then, for example, in the first iteration, at time t=1/4 we are in the bottom-left square. The important thing is that the iterative subdivisions of the curve (that perhaps seem a little... discontinuous) are continuous, in the sense that it will always (i.e. for other iterations) be true that around time $t=1/4$ we will be inside the bottom-left square, and the same applies to the smaller squares: the succesive refinements never take me out of the previous enclosing square for the same time. It should then clear that each square can be put in correspondence to an interval in the parameter $(t_a,t_b) \in [0,1]$, and that succesive nested squares correspond to nested intervals in the parameter $t$.

Returning to our point $x$, it can be uniquely expressed a sequence of enclosed squares (same reasoning as the "nested intervals principle" for reals), which will correspond to a sequence of enclosed intervals in the parameter - and hence they will define a unique real.

Answer 5

I wrote a program to address this question: exploring the hilbert space-filling curve

Here is the image of the interval $[\frac{1}{18}, \frac{1}{\sqrt{2}}]$ of the Hilbert space-filling curve..
Notice it is the union of countably many dyadic squares.

---

The image of the Hilbert curve is invariant under the 4-to-1 map $T:[0,1]^2 \to [0,1]^2$ defined by:

• on $[0, \frac{1}{2}]^2$ turn $90^\circ$ counter clockwise about $(\frac{1}{4}, \frac{1}{4})$ and double both coordinates
• on $[0, \frac{1}{2}] \times [\frac{1}{2}, 1]$ double both coordinates and translate onto the unit square.
• on $[\frac{1}{2}, 1]^2$ double both coordinates and translate onto the unit square.
• on $[\frac{1}{2}, 1] \times [0, \frac{1}{2}] $ turn $90^\circ$ clockwise about $(\frac{3}{4}, \frac{1}{4})$ and double both coordinates

The corresponding map on the pre-image $[0,1] = [0, \frac{1}{4}] \cup [ \frac{1}{4}, \frac{1}{2}]\cup [ \frac{1}{2}, \frac{3}{4}]\cup [ \frac{3}{4}, 1] $ is to multiply by $4$ and translate back to $[0,1]$.

This is equivalent to saying the Hilbert curve is a Lindemayer system.

---

Let's examine the iterations of the Hilbert curve in base 4:

1 2
0 3

and

11 12|21 22
10 13|20 23
-----------
03 02|31 30
00 01|32 33

and

111 112 121 122|211 212 221 222
110 113 120 123|210 213 220 223
103 102 131 130|203 202 231 230
100 101 132 133|200 201 232 233
--------------- ---------------
033 030 023 022|311 310 303 300
032 031 020 021|312 313 302 301
001 002 013 012|321 320 331 332
000 003 010 011|322 323 330 333

The pre-image of a dyadic square of size $\frac{1}{2^k} \times \frac{1}{2^k}$ is the subset of $[0,1]$ with specified the first $k$ digits in the base-4 expansion.

This is how we can establish the existence of a limit-curve and uniform convergence.

We can take a point like $(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$ expand in base 4 and get a well-defined pre-image. Therefore it is space-filling.

Answer 6

Without getting lost in the weeds of technical complexity, you seem to be saying that the Hilbert curve $H^2 \in R^2$ can be loosely described as the set of points $H^2 = \{P(x,y) \in R^2: 0 \le x \le 1 \text { and } 0\le y \le 1\}$ and for every point $P(x,y) \in H^2$ there exists some $k^{\text{th}}$ iteration $H_k^2$ of the Hilbert curve such that $P(x,y)$ is a non-differentiable "corner point". Hence the entire set $H^2 = \lim_{k \rightarrow \infty} H_k^2$ can be described as "pure corner".