COMPUTING SCIENCE

# Crinkly Curves

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

In 1877 the German mathematician Georg Cantor made a shocking discovery. He found that a two-dimensional surface contains no more points than a one-dimensional line. Cantor compared the set of all points forming the area of a square with the set of points along one of the line segments on the perimeter of the square. He showed that the two sets are the same size. Intuition rebels against this notion. Inside a square you could draw infinitely many parallel line segments side by side. Surely an area with room for such an infinite array of lines must include more points than a single line—but it doesn’t. Cantor himself was incredulous: “I see it, but I don’t believe it,” he wrote.

Yet the fact was inescapable. Cantor defined a one-to-one correspondence between the points of the square and the points of the line segment. Every point in the square was associated with a single point in the segment; every point in the segment was matched with a unique point in the square. No points were left over or used twice. It was like pairing up mittens: If you come out even at the end, you must have started with equal numbers of lefts and rights.

Geometrically, Cantor’s one-to-one mapping is a scrambled affair. Neighboring points on the line scatter to widely separated destinations in the square. The question soon arose: Is there a *continuous* mapping between a line and a surface? In other words, can one trace a path through a square without ever lifting the pencil from the paper and touch every point at least once? It took a decade to find the first such curve. Then dozens more were invented, as well as curves that fill up a three-dimensional volume or even a region of some *n*-dimensional space. The very concept of dimension was undermined.

Circa 1900, these space-filling curves were viewed as mysterious aberrations, signaling how far mathematics had strayed from the world of everyday experience. The mystery has never entirely faded away, but the curves have grown more familiar. They are playthings of programmers now, nicely adapted to illustrating certain algorithmic techniques (especially recursion). More surprising, the curves have turned out to have practical applications. They serve to encode geographic information; they have a role in image processing; they help allocate resources in large computing tasks. And they tickle the eye of those with a taste for intricate geometric patterns.

EMAIL TO A FRIEND :