Why does the Hilbert curve fill the whole square?

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.

Hilbert space-filling curve

I suppose the idea is something like this: one defines a sequence of functions fi(t):[0,1]R2, and then considers the pointwise limit f(t)=limifi(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 fi as i increases, and that point might move around, but only by 2i at each stage as we pass from fi to fi+1, and so eventually approaches a limiting position. But I don’t know how we’d get from there to showing that fi(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 fi has at least one rational coordinate, so it is not at all clear why a point like (12,12) 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

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: fn will be the curve obtained by joining the centres of the 4n squares of side 2n according to the proper numbering scheme.

One can make the convention that fn:[0,1][0,1]2, and we represent the part of the line corresponding to the kth square using the interval [(k1)4n,k4n).

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 nth ordering, we obtain the (n+1)th ordering in the following way: the 4n+1 squares are grouped in four main groups of 4n 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 nth numbering, in the following way:

First quadrant: we take the nth numbering, rotate it 90 degrees clockwise and use reverse order.

Second quadrant: we take the nth numbering in its original order (of course, replacing 1 with 4n+1, 2 with 4n+2, etc.

Third quadrant: we take the nth numbering in its original order (of course, replacing 1 with 2×4n+1, 2 with 2×4n+2, etc.

Fourth quadrant: we take the nth numbering, rotate it 90 degrees counter-clockwise and use reverse order, starting with 3×4n+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 {fn} converges uniformly;

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

To prove 1), we note that in the interval [k4n,(k+1)4n), both fn and fn+1 take values in the same square of side 2n. This shows that
|fn+1fn|2n    uniformly.

Regarding 2), if we write f=limfn, 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)[0,1]2. Fix n; then there exists a square from our grid, of side 2n that contains (x,y); say it’s the kth one. Then

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.

Attribution
Source : Link , Question Author : MJD , Answer Author : Martin Argerami

Leave a Comment