The traveling salesman problem (TSP) is an old and wellstudied problem in computer science. Given a collection of cities on a map, a salesman must make a tour of the cities, visiting each once, and returning to the city from which he started. Of all the ways that he could travel from city to city, he must find the one that requires him to travel the least total distance (our salesman is nothing if not frugal). Mathematically, we can view this form of the TSP as finding the minimum length closed path connecting a collection of points in the plane.
The tour that results from a collection of cities tends to have some of the same density properties as the collection itself. In other words, in regions where cities are packed tightly together, you get a lot of traveling in tight little knots; where cities are spaced out, you tend to travel in long straightaways. When the tour is drawn (say, as a black line on a white background), the darkness of the picture will correspond roughly to the density of the cities.
We can exploit this relationship to produce a new halftoning algorithm (halftoning is any process that approximates a continuoustoned image with blackandwhite marks). We distribute cities with a density that locally approximates the darkness of a source image, and pass the cities to a program that finds a TSP tour. The result is a kind of twisty closed path that resembles the original image.
How do we distribute cities? Our goal is to place points in a way that approximates an image. That is itself a form of halftoning, and is a area of computer graphics rich with solutions. We make use of two approaches. Weighted Voronoi stippling uses optimization to space out a collection of points evenly while still conveying image tone. Ordered dithering selectively turns pixels on and off in fixed patterns. Both approaches produce city distributions suitable for the TSP, and yield dramatically different final images.
To produce the final tour, we pass the cities obtained above to the Concorde TSP Solver. We don't try to find the true optimal solution; the reason why we shouldn't expect to do so is what makes the TSP such an interesting problem in computer science! But Concorde produces a heuristic solution that's more than good enough aesthetically. Most importantly, the path it produces never crosses itself; it can be proven that an optimal solution never will.
Once we have the tour, we can draw it pretty easily as a closed polygon. Fancier rendering styles are possible, such as varying the thickness of the lines or curving them.
Chris 
Coliseum 
Mona 
Hummingbird 
Zebra 

David 
Robert Bosch's home page has links to his previous paper on TSP art and sample images.
A couple of years ago, a colleague sent me some photos of billboards in downtown Los Angeles that have images strikingly similar to TSP Art. I'm happy to say that we now know who the artist is. J. Eric Morales (Mo) has a website where you can see his TSP Art images (he calls them "labyrinthine projections").
A couple of TSP Art images appear in the new TSP book by Applegate, Bixby, Chvátal and Cook.
All images are copyright 2005 by Craig S. Kaplan. You are free to use them for personal and noncommercial purposes. Please check with me about any other uses.
Craig S. Kaplan  Last updated: 