In 1890 Giuseppe Peano discovered a planar
curve ^{[1]}
with the rather surprising property that it is "space-filling." The
curve winds around the unit square and hits every point (x, y) at least once.

^{[1]} Recall that a curve is a continuous
map from a one-dimensional space to an n-dimensional
space.

Peano's curve is based on dividing each side of the unit square into three equal parts, which divides the square into nine smaller squares. His curve traverses these nine squares in a certain order. Then, each of the nine small squares is similarly divided into nine still smaller squares, and the curve is modified to traverse all these squares in a certain order. The curve can be described using fractions expressed in base 3; in fact, that's the way Peano first described it.

In 1891 David Hilbert [Hil] discovered a variation of Peano's curve based on dividing each side of the unit square into two equal parts, which divides the square into four smaller squares. Then, each of the four small squares is similarly divided into four still smaller squares, and so on. For each stage of this division, Hilbert gives a curve that traverses all the squares. Hilbert's curve, sometimes called the "Peano-Hilbert curve," is the limit curve of this division process. It can be described using fractions expressed in base 2.

Figure 14-1 shows the first three steps in the sequence that leads to Hilbert's space-filling curve, as they were depicted in his 1891 paper.

Here, we do things a little differently. We
use the term "Hilbert curve" for any of the curves on the sequence
whose limit is the Hilbert space-filling curve. The "Hilbert curve of
order n" means the nth curve in the sequence. In Figure 14-1, the
curves are of order 1, 2, and 3. We shift the curves down and to the left so
that the corners of the curves coincide with the intersections of the lines in
the boxes above. Finally, we scale the size of the order n curve up by a factor of 2^{n},
so that the coordinates of the corners of the curves are integers. Thus, our
order n Hilbert curve has corners at integers
ranging from 0 to 2^{n} - 1 in both x and y. We take the
positive direction along the curve to be from (x,
y) = (0, 0) to (2^{n}
- 1, 0). On the next page are shown the "Hilbert curves," in our
terminology, of orders 1 through 6.