Chapter 14. Hilbert's Curve
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.
Figure 14-1. First three curves in the sequence defining Hilbert's curve.
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 2n, 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 2n - 1 in both x and y. We take the positive direction along the curve to be from (x, y) = (0, 0) to (2n - 1, 0). On the next page are shown the "Hilbert curves," in our terminology, of orders 1 through 6.