Subscribe
Subscribe
MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
Logo IMG
HOME > PAST ISSUE > May-June 2013 > Article Detail

COMPUTING SCIENCE

Crinkly Curves

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

Brian Hayes

Programming by Procrastination

2013-05HayesFD.pngClick to Enlarge ImageThe  illustration at right shows a later stage in the evolution of the Hilbert curve, when it has become convoluted enough that one might begin to believe it will eventually reach all points in the square. The curve was drawn by a computer program written in a recursive style that I call programming by procrastination. The philosophy behind the approach is this: Plotting all those twisty turns looks like a tedious job, so why not put it off as long as we can? Maybe we’ll never have to face it.

Let us eavesdrop on a computer program named Hilbert as it mumbles to itself while trying to solve this problem:

Hmm. I’m supposed to draw a curve that fills a square. I don’t know how to do that, but maybe I can cut the problem down to size. Suppose I had a subroutine that would fill a smaller square, say one-fourth as large. I could invoke that procedure on each quadrant of the main square, getting back four separate pieces of the space-filling curve. Then, if I just draw three line segments to link the four pieces into one long curve, I’ll be finished!
Of course I don’t actually have a subroutine for filling in a quadrant. But a quadrant of a square is itself a square. There’s a program named Hilbert that’s supposed to be able to draw a space-filling curve in any square. I’ll just hand each of the quadrants off to Hilbert.

The strategy described in this monologue may sound like a totally pointless exercise. The Hilbert program keeps subdividing the problem but has no plan for ever actually solving it. However, this is one of those rare and wonderful occasions when procrastination pays off, and the homework assignment you lazily set aside last night is miraculously finished when you get up in the morning.

Consider the sizes of the successive subsquares in Hilbert’s divide-and-conquer process. At each stage, the side length of the square is halved, and the area is reduced to one-fourth. The limiting case, if the process goes on indefinitely, is a square of zero side length and zero area. So here’s the procrastinator’s miracle: Tracing a curve that touches all the points inside a size-zero square is easy, because such a square is in fact a single point. Just draw it!

Practical-minded readers will object that a program running in a finite machine for a finite time will not actually reach the limiting case of squares that shrink away to zero size. I concede the point. If the recursion is halted while the squares still contain multiple points, one of those points must be chosen as a representative; the center of the square is a likely candidate. In making the illustration above, I stopped the program after seven levels of recursion, when the squares were small but certainly larger than a single point. The wiggly blue line connects the centers of 47 = 16,384 squares. Only in the mind’s eye will we ever see a true, infinite space-filling curve, but a finite drawing like this one is at least a guide to the imagination.

There is one more important aspect of this algorithm that I have glossed over. If the curve is to be continuous—with no abrupt jumps—then all the squares have to be arranged so that one segment of the curve ends where the next segment begins. Matching up the end points in this way requires rotating and reflecting some of the subsquares. (For an animated illustration of these transformations, see http://bit-player.org/extras/hilbert.)








comments powered by Disqus
 

EMAIL TO A FRIEND :

Subscribe to American Scientist