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 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 4

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".