William J. Cook

 

On his book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation

Cover Interview of February 13, 2012

A close-up

In the hands of your browsing reader, I’d like the book to fall open to a pair of pages displaying two paintings by Julian Lethbridge, Traveling Salesman and Traveling Salesman 4.  These are not pieces of mathematics, but they capture well the beauty of the salesman problem that attracts so many mathematicians to its study.

A traveler concerned about mileage will not cross her own path during a tour.  Thus a shortest tour can be drawn as a line that loops around but never crosses itself.  Such a line, known as a Jordan curve, divides space into two regions, an inside and an outside.  Think of a fence running around the boundary of a park or think of the coastline of an island.

The first of Lethbridge’s paintings shows vividly the division of space created by a good solution to the salesman problem. Lethbridge uses colors and textures to highlight the interior and exterior, separated by a rendering of the tour itself. The division of space feels natural, suggesting that short tours are, in a sense, organic objects.

The second painting displays the same tour as the first, but highlights the complexity of discovering the partition of space inherent in the locations of the points to be visited. Lethbridge uses multiple colored strokes emanating from each turn of the salesman tour. Following the strokes from point to point, one quickly gets lost in the myriad of alternative paths.