COMPUTING SCIENCE

# Crinkly Curves

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

# All Elbows

In everyday speech the word *curve* suggests something smooth and fluid, without sharp corners, such as a parabola or a circle. The Hilbert curve is anything but smooth. All finite versions of the curve consist of 90-degree bends connected by straight segments. In the infinite limit, the straight segments dwindle away to zero length, leaving nothing but sharp corners. The curve is all elbows. In 1900 the American mathematician Eliakim Hastings Moore came up with the term “crinkly curves” for such objects.

In many respects these curves are reminiscent of fractals, the objects of fractional dimension that Benoit Mandelbrot made famous. The curves’ self-similarity is fractal-like: Zooming in reveals ever more intricate detail. But the Hilbert curve is not a fractal, because its dimension is not a fraction. Any finite approximation is simply a one-dimensional line. On passing to the limit of infinite crinkliness, the curve suddenly becomes a two-dimensional square. There is no intermediate state.

Even though the complete path of an infinite space-filling curve cannot be drawn on paper, it is still a perfectly well-defined object. You can calculate the location along the curve of any specific point you might care to know about. The result is exact if the input is exact. A few landmark points for the Hilbert curve are plotted in the illustration at right (For an interactive version of this illustration, see http://bit-player.org/extras/hilbert/).

The algorithm for this calculation implements the definition of the curve as a mapping from a one-dimensional line segment to a two-dimensional square. The input to the function is a number in the interval [0,1], and the output is a pair of *x, y* coordinates.

The inverse mapping—from *x, y* coordinates to the segment [0,1]—is more troublesome. The problem is that a point in the square can be linked to more than one point on the line.

Cantor’s dimension-defying function was a *one-to-one* mapping: Each point on the line was associated with exactly one point in the square, and vice versa. But Cantor’s mapping was not continuous: Adjacent points on the line did not necessarily map to adjacent points in the square. In contrast, the space-filling curves are continuous but not one-to-one. Although each point on the line is associated with a unique point in the square, a point in the square can map back to multiple points on the line. A conspicuous example is the center of the square, with the coordinates *x*=1/2, *y*=1/2. Three separate locations on the line segment (1/6, 1/2 and 5/6) all connect to this one point in the square.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Engineering**: Traffic Signals, Dilemma Zones, and Red-Light Cameras

**Perspective**: Taking the Long View on Sexism in Science

**Computing Science**: Computer Vision and Computer Hallucinations