A Line That Fills a Square

As Many Points

In 1877 Georg Cantor proved that the points of a segment and the points of a square can be paired off one to one, none left over on either side. He published it the next year.

The idea is to interleave digits. Write a point of the line as t = 0.a₁a₂a₃a₄…, give the odd digits to x and the even ones to y: (0.a₁a₃…, 0.a₂a₄…). It can be read back the other way. Richard Dedekind replied that some numbers have two decimal expansions, so plain interleaving does not quite work; Cantor then corrected the proof.

In a letter to Dedekind he wrote “I see it, but I don’t believe it.” The line is often read as astonishment; the historian Fernando Gouvêa argues that Cantor was worried whether the proof had a gap.

The pairing is not continuous. Neighbours on the line, 0.4999 and 0.5000, land near the top edge and on the bottom edge of the square. In 1879 Eugen Netto proved that no map between a segment and a square is both one to one and continuous.

Through Every Point, Continuously

Give up one to one and ask only for continuity: can a line pass through every point of a square? In 1890 Giuseppe Peano gave the first example.

He split the segment into 9 pieces and the square into 3 × 3 cells, the k-th piece to the k-th cell, neighbouring pieces to neighbouring cells; then each cell into 9 again, without end. His definition is all arithmetic on base-3 digits; the paper has no picture.

The wire in the tray is the second step: 81 cells in one stroke, each step to a neighbouring cell. Curves made this way are called space-filling curves.

Hilbert’s Picture

The next year David Hilbert published a two-page note in the same journal, with a figure. He split into four each time: the segment into quarters, the square into 2 × 2, the four pieces to the four cells in turn, neighbouring pieces to cells that share a side.

Each cell is split into four again, and the curve repeats the same ∩ inside it; in the first and last cells it is turned so the ends join up. Then on, without end.

The wire of step n passes through the centres of 4ⁿ cells. At each step, the short stretch in each cell is replaced by a small ∩.

The rod in front is the segment [0, 1]. Its colours match the cells in the tray: each stretch of the line is a patch of the square.

The Limit

In a square of side 1, the wire of step n is 2ⁿ − 2⁻ⁿ long: about twice as long at each step, without bound. The Hilbert curve is none of the wires; it is their limit.

Yet the place of each t settles down. The wire of step n is nowhere farther from the limit than a cell’s diagonal, √2 / 2ⁿ, so the steps converge uniformly and the limit H(t) is continuous: change t a little, and H(t) moves only a little.

The bead sits at t = 0.3. With each step it moves a shorter way, and comes to rest near H(0.3).

Some Points, Three Times

Pick any point of the square. At each step some cell contains it; the stretches of the line for those cells nest inside each other and shrink to one t, and H(t) is that point. So no point is missed.

Some points are passed more than once. The centre of the square is a corner of four small squares, and the curve passes it three times: at t = 1/6, 1/2 and 5/6, in binary 0.0010101…, 0.1 and 0.1101010….

This is no flaw of this curve. By Netto’s theorem, any continuous curve through every point of the square must pass some points more than once.

Near Stays Near

A short stretch of the line lands in the square as a small patch. The lit cells in the tray are 64 in a row along the curve, and they always crowd into an area of about 8 × 8.

Measured on the curve of step 8: two cells whose numbers differ by k are never more than √(6k) cells apart. 6 is the exact constant for the Hilbert curve under this measure (Haverkort and van Walderveen, 2010).

The converse fails. Two cells side by side in the square can have numbers far apart: across the middle line, one lies in the first half of the curve and its neighbour in the second. Any way of putting a square in a line has places like this.

Z-Order

Interleave the binary digits of x and y and you get the Z-order number, or Morton code. G. M. Morton of IBM Canada proposed it in 1966 for a geographic database. It is Cantor’s interleaving again, in binary.

Every four cells make a Z, and four small Zs a large one. It is very fast to compute, but at the end of each block it has to jump to the next: in the right-hand tray the wire leaves the floor there and arches across. The largest jump nearly crosses the whole square.

So the limit of Z-order is not a continuous curve. The same 16 consecutive numbers are always one small patch on the Hilbert curve, and in Z-order sometimes several patches far apart; the readout gives how far apart the two farthest cells lie on each.

Its simplicity makes it common. Bing Maps interleaves the bits of a map tile’s row and column to name the tile (its quadkey).

A Family of Curves

In 1900 E. H. Moore joined four Hilbert curves end to end into a closed curve: after one round it comes back beside its start.

Peano’s curve splits into nine each time and runs as a serpentine. The same idea works with triangles, or with blocks of different sizes.

The dragon curve comes from folding paper: fold a strip in half, and in half again, then open every crease to a right angle. It does not fill a square, but four dragons from one point, each turned by 90°, run along every line of squared paper exactly once (Davis and Knuth, 1970).

Scanning Along the Curve

To turn a grey image into black and white dots, one method is error diffusion: each dot becomes black or white, and the rounding error is passed on to the next dot.

Scanning row by row pushes the error the same way every time, and stripes appear. Along the Hilbert curve the next dot is always close by and the direction keeps changing, so the error spreads more evenly (Velho and Gomes, 1991).

In the tray the bead runs along the wire through 4096 cells and settles each one black or white as it passes. This is the simplest version: the whole error goes to the next cell.

Maps and Databases

A database keeps its records in one-dimensional order. Number two-dimensional places along a space-filling curve and places near each other mostly sit near each other, so a query reads a few runs of consecutive records.

The red frame in the trays is a query. Its cells fall into a number of runs on the line; both trays show the actual count for this frame, and the Hilbert curve usually needs fewer than Z-order.

In 1994 Ibrahim Kamel and Christos Faloutsos ordered the nodes of an R-tree by Hilbert number: the Hilbert R-tree. Matrices and images are also often stored in blocks in Z-order or Hilbert order, so neighbouring elements sit closer in memory.

Cells on a Sphere

Google’s S2 geometry library numbers the Earth’s surface like this: project the sphere onto the six faces of a surrounding cube, and split each face into four along a Hilbert curve, up to 30 levels deep.

Six Hilbert curves joined end to end run once round the sphere as a closed curve; neighbouring faces run as mirror images so the ends meet. A cell’s 64-bit number is the position of its centre along that curve.

Cells at level 30 average 0.74 cm², 6 to 9 mm on a side, about 6.9 × 10¹⁸ in all. To keep the cells close in size, coordinates on the cube go through a quadratic function before they are projected onto the sphere.