Never Lift the Pencil

Have you ever tried drawing something without lifting your pencil from the paper? You usually end up with a squiggly mess that sometimes looks a bit like the object you were trying to draw.

Now computer scientists have written a program that does first-rate "continuous-line" drawings. Why are they wasting their time on such frivolous things? The answer is that the drawings are actually a version of an important mathematical problem that turns up in many everyday situations.


A continuous-line version of Leonardo da Vinci's Mona Lisa portrait.

Suppose you're at a humongous mall with dozens of stores. You need to visit nine of them to find that Naruto manga you put down somewhere, before your mom arrives to pick you up. What's the shortest route between all nine stores and the mall entrance?

One way to solve the problem is to get out a map of the mall, locate the entrance and the nine stores you need to visit, and measure all the different distances. You can then list the possible routes, calculate the length of each route, and pick the shortest one.

Whew! That sounds like a lot of work, and it is. In fact, you would have to check 362,880 (9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1) possibilities. As the number of stores increases, the number of possibilities skyrockets. Imagine how many there would be if you were to visit all 99 stores in the mall.

Mathematicians and engineers often have to make such calculations, whether to design networks carrying phone calls across the country, to plan routes for shipping goods from a warehouse, or to create schedules. Over the years, they've developed efficient ways to solve problems of this type.

The current world record for such a calculation is a route that visits all 24,978 cities, towns, and villages in Sweden. Despite the efficient method, finding that route took a lot of computer time!

You can see the Swedish tour at http://www.tsp.gatech.edu/sweden/index.html (Georgia Tech).

Robert Bosch and Adrianne Herman of Oberlin College in Ohio use a similar method to make continuous-line drawings of celebrities, works of art or architecture, or friends. Their computer program starts with a black-and-white digital image. The picture is divided into squares, and an average darkness is computed for each square.

Then a blank digital "canvas" is divided into matching squares, and a computer randomly places points (the "cities") within each square. The number of points in a square is related to the square's darkness. Next, distances between the points are computed.

Finally, the program then solves the problem of visiting all those points, one by one, to produce a route. Voila! It produces a continuous-line drawing, which from a distance actually looks a bit like the original image.

For more on continuous-line drawings, go to http://www.oberlin.edu/alummag/spring2004/ats.html (Oberlin College).

Robert Bosch's domino artworks are featured in the MatheMUSEments article Seeing Spots.

---

Muse, April 2005, p. 17.