TSP Art

[penguins]

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

Other resources

Ivars Peterson wrote an article about TSP Art for the April 2005 issue of Muse Magazine. Note that the article falsely attributes the technique to Robert Bosch and Adrianne Herman. They worked together on an earlier version of TSP art; all the pictures here (and the penguins that appear in the magazine) were produced by a more recent collaboration between me and Robert. The magazine will publish a correction in late 2005.

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 non-commercial purposes. Please check with me about any other uses.


Craig S. Kaplan Last updated: