TSP Art

The traveling salesman problem (TSP) is an old and well-studied 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 continuous-toned image with black-and-white 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.

Gallery

Here are several sample images of TSP Art. Clicking on each one will open a PDF of the same image (because this is line art, the PDFs work much better). Some results are based on photographs by Phil Greenspun.

Chris	Coliseum
Mona	Hummingbird
Zebra
David

Papers

• TSP Art. Bridges 2005.

Other resources

My co-author, Robert Bosch, has continued to explore many fun and beautiful variations on TSP Art. See his page on the subject for more, and find him on Twitter, where he frequently posts images created using TSP Art and other optimization techniques.

Karan Singh at the University of Toronto developed a completely different technique that can produce similar images, and many others besides. See his page on mazes for more.

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.