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.


TSP Art Last updated: 7-Aug-2006