TSP art

TSP art is a way of drawing a picture with one closed line that never crosses itself. Dots are scattered over the paper, more where the picture is dark, and a single line is drawn through all of them as short as possible. Finding that line is the travelling salesman problem. The method was introduced by Robert Bosch and Adrianne Herman in 2004, in a two-page paper in Operations Research Letters.¹

The travelling salesman

The travelling salesman problem asks for "the shortest possible route that visits each city exactly once and returns to the origin city". It is NP-hard: no known method finds the best route quickly once there are many cities.² The best route can never cross itself, since two crossing stretches can always be swapped for two shorter ones, so it is "guaranteed to be a simple, closed polygon".¹ A line that visits dots packed close together stays close together, and the picture appears.

How it works

Craig S. Kaplan and Bosch describe it as two optimisations, one after the other: first place the dots, then link them.¹

Placing the dots. In Bosch and Herman's grid method, the picture is divided into small square cells. Each cell gets a number of dots that depends on its mean brightness: none where it is white, up to a chosen maximum where it is black. The dots are put at random places inside the cell.¹

Linking them. Bosch and Herman passed the dots to the Lin–Kernighan solver in the Concorde program, which finds a route that is "probably not optimal, but that is almost always simple".¹

Better dots. Randomly placed dots can lie very close to each other and give short, jagged bits of line. Kaplan and Bosch got tidier drawings, with fewer dots, by placing them with weighted Voronoi stippling, which spaces the dots evenly.¹

New drawing

The Mona Lisa

In February 2009 Bosch made a TSP problem of 100,000 dots from the Mona Lisa. The University of Waterloo offers 1,000 dollars to anyone who finds a shorter route than the best known one, found by Yuichi Nagata in March 2009. Computation has shown that the best possible route can be at most 107 units shorter, out of 5,757,191.³ Bosch, a professor of mathematics at Oberlin College, collected such drawings in the book Opt Art (Princeton University Press, 2019).⁴

On a plotter

A TSP drawing is ideal for a pen plotter: the pen goes down once and comes up once. The free program StippleGen from Evil Mad Scientist Laboratories places the dots with weighted Voronoi stippling and can "generate a TSP path from the stippled image" for their drawing machines.⁵ The same problem in its everyday form, putting the separate lines of an ordinary drawing in a good order, is described in plotter path optimisation.