COMPUTING SCIENCE

# Crinkly Curves

Some curves are so convoluted they wiggle free of the one-dimensional world and fill up space

# Grammar and Arithmetic

The procrastinator’s algorithm is certainly not the only way to draw a space-filling curve. Another method exploits the self-similarity of the pattern—the presence of repeated motifs that appear in each successive stage of the construction. In the Hilbert curve the basic motif is a U-shaped path with four possible orientations. In going from one stage of refinement to the next, each U orientation is replaced by a specific sequence of four smaller U curves, along with line segments that link them together, as shown in the illustration at right. The substitution rules form a grammar that generates geometric figures in the same way that a linguistic grammar generates phrases and sentences.

The output of the grammatical process is a sequence of symbols. An easy way to turn it into a drawing is to interpret the symbols as commands in the language of “turtle graphics.” The turtle is a conceptual drawing instrument, which crawls over the plane in response to simple instructions to move forward, turn left or turn right. The turtle’s trail across the surface becomes the curve to be drawn.

When Peano and Hilbert were writing about the first space-filling curves, they did not explain them in terms of grammatical rules or turtle graphics. Instead their approach was numerical, assigning a number in the interval [0,1] to every point on a line segment and also to every point in a square. For the Hilbert curve, it’s convenient to do this arithmetic in base 4, or quaternary, working with the digits 0, 1, 2, 3. In a quaternary fraction such as 0.213, each successive digit specifies a quadrant or subquadrant of the square, as outlined in the illustration at right.

What about other space-filling curves? Peano’s curve is conceptually similar to Hilbert’s but divides the square into nine regions instead of four. Another famous example was invented in 1912 by the Polish mathematician Waclaw Sierpinski; it partitions the square along its diagonals, forming triangles that are then further subdivided. A more recent invention is the “flowsnake” curve devised in the 1970s by Bill Gosper.

Filling three-dimensional space turns out to be even easier than filling the plane—or at least there are more ways to do it. Herman Haverkort of the Eindhoven Institute of Technology in the Netherlands has counted the three-dimensional analogues of the Hilbert curve; there are more than 10 million of them.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Engineering**: Aspirants, Apprentices, and Student Engineers

**Spotlight**: New Information from Ancient Genomes

**Spotlight**: First Person: Joan Strassmann