Hacker's Delight

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