Making TSP Art
Step 1: Select a target image.
Step 2: Lay down some dots.
Step 3: Connect the dots.
Comments
1. Steps 2 and 3 give rise to Euclidean TSP instances.
In our example, there are 2006 dots. We can think of these dots
as cities, the 2006 cities of the fair realm of Smileyland. And we can
imagine that a salesman, who resides in one of the cities, needs to visit
each of the other cities exactly once and then return home. The salesman,
being concerned about his impact on the environment, would like to visit
the cities in an order that will minimize the total length of his tour
(as this will minimize the amount of fuel he consumes and the amount
of pollutants his vehicle emits into the atmosphere).
Note that while finding the total length of a given tour is
very easy to do (we simply add up the lengths of the 2006 tour segments),
finding an optimal tour, the best order in which to visit
the cities, is extremely difficult. After all, there are 2005!
possible tours that the salesman could take! Evaluating every one of
them is completely out of the question!
This problem, of determining an optimal itinerary for the saleman,
is an instance of the
Traveling Salesman Problem,
one of the most well-known and well-studied problems in mathematics,
computer science, and operations research. Actually, the TSP instances
we generate in TSP Art are Euclidean TSP instances.
(In Smileyland, the salesman can travel "as the crow flies", so
the lengths of his tour segments can be computed using the standard
Euclidean distance formula).
2. Take care when laying down the dots!
In 2003, when Adrianne Herman and I first started making TSP Art, we used
a grid-based method. The method was simple but required many dots to produce
a decent picture. (The dots tended to clump together.) In 2004,
Craig S. Kaplan had
the brilliant idea of using
weighted Voronoi stippling.
With weighted Voronoi stippling, substantially fewer dots are needed.
Also, the resulting TSP tours have a much more organic appearance.
To see some of Craig's TSP Art (and find a link to a paper we wrote
together), go to Craig's marvelous
TSP Art page.
3. Use a good heuristic!
To solve the TSP instances, we use the
Concorde TSP Solver's
implementation of the Lin-Kernighan heuristic, which tends to produce very
high quality (i.e., close-to-optimal) tours. We strongly recommend using
a high quality heuristic; here's what happened when
we used Nearest-Neighbor:
Yuck!
3. The Jordan Curve Theorem.
Euclidean TSP instances have a very nice property: their optimal tours
are guaranteed to be closed simple curves (loops). The
Jordan Curve Theorem
states that any simple closed curve in the plane separates the plane into
two regions: the part that lies inside the curve, and the part that lies
outside it.
But it is not always easy to determine whether a point is inside
the curve! For example, is the red dot in the picture below
inside the curve?
It turns out that the answer is yes!
All images are copyright 2006 by Robert Bosch. You are
free to use them for personal and non-commercial purposes.
Please check with me about any other uses.