|
MatheMUSEments
Never Lift
the Pencil
By Ivars Peterson
Muse, April 2005, p. 17.
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!
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.
You can see the Swedish tour at
http://www.tsp.gatech.edu/sweden/index.html (Georgia Tech).
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.
|
SNK RSS Feed 
