[Prev][Next][Up]VSFCF - CVM 1.1[Bib][Respond][Find][Help]

Definition of the Hilbert Curve

The Hilbert curve can be completely, analytically described with iterated functions as follows. Consider four maps from the unit square region to itself: f0 and f3 shrink by a factor of 1/2 toward the lower left corner and lower right corner respectively and reflect across the diagonal to that corner, while f1 and f2 shrink by the same factor toward the upper left and upper right corners respectively. Then the Hilbert curve is the map from the unit interval onto the unit square that takes the point with base 4 expansion x=0.a1a2a3... to the limit of fa1 fa2 fa3···fan(y) as n goes to infinity (where y is any point in the plane - or, in fact, any nonempty bounded set in the plane). These functions also can be efficiently described using complex numbers:

f0(z)=z*i/2,     f1(z)=(z+i)/2,     f2(z)=(z+i+1)/2,     f3(z)=(-i z*+i)/2+1         (2)

where * represents complex conjugation of the immediately preceding number. Furthermore, by standard facts (essentially the Contraction Mapping Theorem) about iterated function systems (see [Ba, p. 82] ), if we start with any compact set in the plane and take the union of all possible applications of n of these functions (with repetitions), as n increases the image will converge (in Hausdorff distance) to the image of the Hilbert curve (the filled in unit square). By being more careful about how we apply these functions, we can, with certain restrictions, get a large family of curves that converge as functions (not just their images) to the Hilbert curve. As described by Sagan ([Sag, p. 23]), starting with any curve g with initial point 0 and terminal point 1 we can build curves using the fk that converge uniformly to the Hilbert curve. Namely, for the nth approximation, cut the unit interval into 4n congruent segments. Map the kth subinterval, k=0,1,...,4n-1, where k=a1a2...an base 4 (leading aj's may be 0) by the composition fa1 fa2···fang following a direct linear stretching of the subinterval to the full unit interval. In Figure 4 we show the first four images of maps approximating the Hilbert curve based on a fairly arbitrary map of the unit interval from 0 to 1 (g(x)=x-i x2(1-x)sin(2p x)/4).

graph of g 1st iteration of IFS
2nd iteration of IFS 3rd iteration of IFS
Figure 4. The graph of g and the first three iterations of the Hilbert IFS applied to the graph. Also available is an animation (131kb) with the first 8 iterations and a speed controlled applet. In any case, one gets a discrete jerky animation, much like Figure 1. Use the browser back button to return. Source code is available.

We generalize this construction to any starting curve so as to include Hilbert's original curve by adding appropriate connecting segments. Let g be any continuous curve from the unit interval to the plane. For each natural number n divide the unit segment [0,1] into alternating segments of nonnegative lengths bn and cn so that there are 4n segments of length bn and 4n-1 of length cn. (We only allow cn to be zero in the case when g has initial point 0 and terminal point 1. In fact, this choice will just give us the previous case.) On the segments of length bn we proceed as before: for the kth such interval (k starts counting at 0) we map the interval linearly and directly onto the unit interval, follow this by the given function g, and then follow this by the element of the IFS corresponding to k; namely for k= a1a2a3...an base 4 we follow g by the composition fa1 fa2 fa3···fan. On the kth intermediate, length cn interval, we use the linear map that connects the terminal point of the function now defined on the kth length bn interval to the initial point of the function now defined on the (k+1)st length bn interval. By choosing g to be the constant map to the center of the unit square (g(x)=(1+i)/2) and all bn=0 we get exactly Hilbert's original definition of approximating curves as drawn in Figure 1. However, we now have the following:

Theorem. For any choices above of g, bn, and cn, with the IFS constructed as indicated, the limiting function will be precisely the classical Hilbert curve (even though the intermediate approximating curves will usually be different from the classical approximating curves).

Proof. The four IFS functions for the Hilbert curve have the property that if a1a2··· an and a'1a'2··· a'n are base four expansions of consecutive whole numbers, then F=fa1 fa2··· fan and F'=fa'1 fa'2··· fa'n map the unit square to adjacent squares of side length 1/2n. Let X be a disk of width (diameter) W that contains the unit square and the graph of g. Then any points of F(X) and F'(X) are inside a single disk, Z, of width W/2n-1 since each function shrinks by a factor of 1/2n and this gives us two meeting disks each of width W/2n. Now for a given n, we have two different approximations of the Hilbert curve: the classical nth approximation and the general version we've been considering. Fix any x in the unit interval. In the classical approximation, we have all bn = 0 and x is in say the kth subinterval of length cn. Let a1a2··· an be the base four expansion of k, defining F and F' as above. The classical nth approximation maps the endpoints of this interval to F((1+i)/2) and F'((1+i)/2). In particular, they are mapped into Z and the whole interval of length cn (including x) will be mapped to the interval connecting them. Since Z is convex, we have x mapped into Z by the classical nth approximation to Hilbert's curve.

In the generalized approximation, x will lie in either the kth or (k+1)st interval of length bn or in the kth interval of length cn. In the first two cases, we map x into the unit interval when we stretch the interval of length bn, then map it into X with g, and then apply either F or F' depending which of the two cases we're in. So x is mapped into Z. If x is in the kth interval of length cn, then it is mapped into a line segment in Z and so lies in Z in this case too.

Thus both approximations are within W/2n-1 of each other, and since the classical one converges to the Hilbert curve as n goes to infinity, the generalized one must also. qed

We now vary our four IFS functions. We'll let hk be fk followed by a homothetic shrinking toward the corner that's the fixed point of fk. More precisely:

h0(z)= sz*i,     h1(z)= sz+(1-s)i,     h2(z)= sz+(1-s)(i+1),     h3(z)= (1-z*)si+1         (3)

which reduces to the definition of the fk in (2) for s=1/2. For s strictly between 0 and 1/2 the attractor of the IFS defined by the four hk functions will be a Cantor set of similarity dimension -1/log4s as follows. For fixed s between 0 and 1/2, let C0 be the unit square region. Let C1 be the union of the four square regions of side length s in each corner of C0 and continue in this way. Alternatively, Cm+1 is just the union of the four sets hk(Cm) for k=0,1,2,3. Then the intersection of the nested Cm will be a Cantor set that is the attractor of the IFS defined by the hk. (This is a common situation with IFS's. If we can find a compact set such that the IFS function images are pairwise disjoint subsets of it, then this type of intersection will be the attractor.) Note that this intersection is clearly not empty; for example the corner points at any stage will all be in the intersection. Now this attractor (see Figure 5) is self similar to four smaller copies with ratio s. So the self-similar dimension, D, satisfies 4sD=1 and so D=-1/log4s.

The attractor of the IFS defined by {h0, h1, h2, h3} will be a Cantor set that is itself the Cartesian product of two Cantor sets that are produced by deleting the open middle (1-2s) part of each interval in each stage of the construction. This is shown in Figure 5 where on the left we have s=1/3 (standard middle third Cantor set) and on the right s=2/5 (middle fifth deleted). Apparent non-similarity arises from "pixel round off error" - since we must draw or omit complete pixels at each stage (see Section 12 for a discussion).

 frame 10 of 16  frame 12 of 16
Figure 5. Frames corresponding to s=1/3 and s=2/5 in 16 frame animation of Cartesian product of Cantor sets. The extreme cases, s=0,1/2 are produced by the same algorithm, but are not Cantor sets. Also available is an animation (84kb) and a speed controlled version. Use the browser back button to return. Source code is available.
Thus, as s varies from 0 to 1/2 the Cantor set attractor varies in dimension from 0 to 2. We can make this Cantor set into a curve by adding in connecting segments as in Figure 6. This will increase the dimension to 1 for s<1/4 and won't change the dimension for other values of s. (This figure is different but reminiscent of the figure on page 194 of [Ed]. There are also some similarities to the figures in Wang and Li ([WL]).)

3kb frame 10/20 7kb frame 15/20
Figure 6. Frames 10 and 15 of 20 in animation of curves of increasing dimension to Hilbert curve. Also available is a full big animation (202kb) and a speed controlled version; use the browser back button to return. Source code is available.

[Next] Connection to the Cantor Set
[Up] Table of contents
[Prev] The Snowflake Curve

Communications in Visual Mathematics, vol 1, no 1, August 1998.
Copyright © 1998, The Mathematical Association of America. All rights reserved.
Created: 18 Aug 1998 --- Last modified: Sep 30, 2003 6:26:00 PM
Comments to: CVM@maa.org