Joining the dots
A travelling salesman tour of the Mona Lisa
Ìý
The beauty of mathematics is essentially abstract, describing the aesthetic joy of a particularly clever proof or an unexpected result.
Yet some mathematics leads to a more traditional kind of beauty, the kind you might see in a piece of art.
Few research areas combine mathematical and visual beauty quite like the travelling salesman problem � a very simple problem that touches on incredibly deep maths, and generates gorgeous illustrations some of which have indeed hung in galleries.
The travelling salesman problem, or TSP, is the problem faced by a travelling salesman who must visit several cities and design the shortest route between them. The salesman must return to where he started after visiting each city only once.
As William J Cook explains in his fantastic new book,, the TSP is interesting to the mathematical community because it is so goddam hard!
To try to find the shortest route between 33 cities you need choose between
131,565,418,466,846,765,083,609,006,080,000,000 possible routes.
(And this is not because there are lots of different roads � we are considering only direct lines between the cities).
If we were comparing them one by one, and using, say, IBM’s Roadrunner supercomputer, one of the most powerful computers in the world, it would still take 28 trillion years to solve. Since the Earth has maybe only, this is evidently not ideal.
Cook tells the story of the race to solve the travelling salesman problem, as mathematicians thought up ingenious strategies � and also were helped out by increasing computer power.
In 1954, the fastest route between 48 US cities was known (It is shown on the cover of Cook’s book). In 1977, the TSP was solved for 120 cities. By 1992, the optimal route between 3038 cities had been calculated and the current record is a tour of 85,900 cities, calculated in 2006 using software called Concorde.
The ultimate travelling salesman problem � between all 1,904,711 cities, towns and villages in the world is still an open problem.
While the theoreticians were concerning themselves with the maths, other mathematicians saw that the TSP algorithms could provide remarkable artworks.The basic idea is to draw a number of dots and then just link them using the shortest possible line. In other words, each city is a dot, and the quickest tour of the cities provides you with an arresting image.
Here are some great examples:
Traveling Salesman, Julian Lethbridge, 1995
Because the salesman always returns to the starting point, you always get a closed curve, which means there is an inside and an outside. Here the inside of the curve is dark red and the outside lighter red.
A similar pattern can be seen in the artwork below. The artist Philip Galanter explains in some detail the maths behind the image
Ìý
mural by Philip Galanter
The gurus of TSP art however are the computer scientists and . (Click on their names to see their sites) Robert’s Mona Lisa below is created by placing 100,000 dots on a blank screen depending on the colour of the original painting, and then asking a computer to join them up in the shortest possible line. The solution is not optimal, however, meaning that there might be a solution with a shorter line, and if you find it Robert and William Cook are offering a Good luck!
POSTSCRIPT: William Cook has just launched a TSP app for iPhone and iPad, as a companion to the book. You can see how it finds the shortest route between a selection of random dots.
