Hacker’s Delight, Second Edition

Chapter 16. Hilbert’s Curve

In 1890, Giuseppe Peano discovered a planar curve¹ 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.

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