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

Math on Wheels

Space-filling curves have been called monsters, but they are useful monsters. One of their most remarkable applications was reported 30 years ago by John J. Bartholdi III and his colleagues at the Georgia Institute of Technology. Their aim was to find efficient routes for drivers delivering Meals on Wheels to elderly clients scattered around the city of Atlanta. Finding the best possible delivery sequence would be a challenging task even with a powerful computer. Meals on Wheels didn’t need the solution to be strictly optimal, but they needed to plan and revise routes quickly, and they had to do it with no computing hardware at all. Bartholdi and his coworkers came up with a scheme that used a map, a few pages of printed tables and two Rolodex files.

Planning a route started with Rolodex cards listing the delivery addresses. The manager looked up the map coordinates of each address, then looked up those coordinates in a table, which supplied an index number to write on the Rolodex card. Sorting the cards by index number yielded the delivery sequence.

Behind the scenes in this procedure was a space-filling curve (specifically, a finite approximation to a Sierpinski curve) that had been superimposed on the map. The index numbers in the tables encoded position along this curve. The delivery route didn’t follow the Sierpinski curve, with all its crinkly turns. The curve merely determined the sequence of addresses, and the driver then chose the shortest point-to-point route between them.

A space-filling curve works well in this role because it preserves “locality.” If two points are nearby on the plane, they are likely to be nearby on the curve as well. The route makes no wasteful excursions across town and back again.

2013-05HayesFI.pngClick to Enlarge ImageThe Meals on Wheels scheduling task is an instance of the traveling salesman problem, a notorious stumper in computer science. The Bartholdi algorithm gives a solution that is not guaranteed to be best but is usually good. For randomly distributed locations, the tours average about 25 percent longer than the optimum. Other heuristic methods can beat this performance, but they are much more complicated. The Bartholdi method finds a route without even computing the distances between sites.

Locality is a helpful property in other contexts as well. Sometimes what’s needed is not a route from one site to the next but a grouping of sites into clusters. In two or more dimensions, identifying clusters can be difficult; threading a space-filling curve through the data set reduces it to a one-dimensional problem.

The graphic arts have enlisted the help of space-filling curves for a process known as halftoning, which allows black-and-white devices (such as laser printers) to reproduce shades of gray. Conventional halftoning methods rely on arrays of dots that vary in size to represent lighter and darker regions. Both random and regular arrays tend to blur fine features and sharp lines in an image. A halftone pattern that groups the dots along the path of a Hilbert or Peano curve can provide smooth tonal gradients while preserving crisp details.

Another application comes from a quite different realm: the multiplication of matrices (a critical step in large-scale computations). Accessing matrix elements by rows and columns requires the same values to be read from memory multiple times. In 2006 Michael Bader and Christoph Zenger of the Technical University of Munich showed that clustering the data with a space-filling curve reduces memory traffic.

Bader is also the author of an excellent recent book that discusses space-filling curves from a computational point of view. An earlier volume by Hans Sagan is more mathematical.

Given that people have found such a surprising variety of uses for these curious curves, I can’t help wondering whether nature has also put them to work. Other kinds of patterns are everywhere in the natural world: stripes, spots, spirals and many kinds of branching structures. But I can’t recall seeing a Peano curve on the landscape. The closest I can come are certain trace fossils (preserved furrows and burrows of organisms on the sea floor) and perhaps the ridges and grooves on the surface of the human cerebrum.




comments powered by Disqus
 

EMAIL TO A FRIEND :

Subscribe to American Scientist