Traveling salesman art

Bill Cook sent me a file yesterday that renders the Endeavour photo on my blog as the solution to a 66,290-city Traveling Salesman problem. His iPhone app Concord TSP chose 66,290 points and then solved for the shortest path connecting these points, a feat that would have strained a supercomputer a few years ago. (Bill Cook and I are not related as far as I know.)

Here is a thumbnail image of the full TSP tour:

You can find the full PDF here (1.24 MB). To show some of the detail, here is a close-up from near the top-left corner of the image:

I asked how the tour was constructed:

How do you construct a set of points whose TSP solution resembles a photograph? Is it sufficient to add more “cities” in regions where you want darker shading? And are the cities added at random with a density specified by color depth?

Bill Cook replied:

By default, the app will select the points along the line you describe: it splits the image into a grid, computes the average gray scale in each grid region, and drops a number of random cities into each grid region in proportion to the square of the average gray scale. This technique was first proposed by Bob Bosch and Adrianne Herman at Oberlin College. It is the default since it takes almost no time to compute, but I include two other options, that each take about a minute to render a large image on an iPhone 4.

The image of The Endeavour was created with a method Jim Bumgarnder proposed in his Stipple Cam project.

Related post:

Moore’s law squared

Tagged with:
Posted in Computing, Math
7 comments on “Traveling salesman art
  1. Scott says:

    This is fascinating. Is this the precise solution to this 66,290-city Traveling Salesman problem, or merely a good solution? I had no idea such large Traveling Salesman problems were computer solvable in such a short time. What has changed in recent years that a problem that would strain supercomputers a few years ago can now be whipped out by an iPhone app?

  2. Presumably, this is *not* a provably optimal TSP solution.

  3. Bill Cook says:

    The tour was found with 500 iterations of the Chained-Lin-Kernighan heuristic. It typically gives a very good solution, but not optimal for such a large instance.

  4. Phil H says:

    I can think of a use for this algorithm: sending raster images to vector printers! Both laser printers and pen plotters use line paths to turn greyscale raster images into two-tone plots which they can scan with their pen/laser.

    Why travelling salesman? Well, a shorter path should be quicker to print, and it doesn’t need to be optimal, just reasonable.

    Who’s got a plotter?

  5. Edward Kmett says:

    If you poke two holes in the edges of the TSP solution you wind up with a maze, since an optimal or near-optimal planar TSP solution can be continuously deformed without crossing into a circle. (Otherwise you can hill climb by swapping some edges to make a better solution and concorde is smart enough to have already done so)

    I used this approach (and concorde for what its worth) several years back to make mazes for a linguist list fund drive out of images and there has been at least one paper written on the topic.

    The nice thing is you get to know that a solution exists, but you don’t get direct knowledge of what the solution is — not that it is that hard to find with a pathfinding algorithm after the fact.

    There is, sadly, some bias in this approach though, since the number of points in a given unit area is only fairly loosely correlated to the amount of ink spent on paths moving through that area.

    You may also be interested in the first paper I saw on the topic:

    http://www.cgl.uwaterloo.ca/~csk/papers/kaplan_bridges2005b.pdf

  6. Johannes says:

    This method of generating greyscale »images« was recently also mentioned over at Evil Mad Scientist Labs. There the problem was essentially how to draw an image efficiently on an egg, where TSP paths provide a nice solution that does not need any pen lifting while still providing lighter and darker areas in the image.

4 Pings/Trackbacks for "Traveling salesman art"
  1. [...] Traveling Salesman Art [...]

  2. [...] Cook on Traveling Salesman art, based on a traveling salesman app, which is a companion to Bill Cook’s book In Pursuit of [...]

  3. 超级数学APP:秒解旅行商问题…

    旅行商问题(Travelling Salesman Problem) 是一个著名的NP-Hard问题,往往是初学信息学的人就能听说的(其实我不是学信息学的)。NP-Hard问题都是很难的、计算起来很慢的吗?这里有一个苹果产品app (for iPhone , iPad, iPod Touch) ,居然能够以超快的速度解出旅行商问题,甚至用它的解画出图案来!比如: 这张图是一个66290个城市间的旅行商问题的解,仅仅由点和线段组成。放大一点是这样: 很酷吧!让无数人挠头的旅行商问题竟然可以用来绘制抽象…

  4. [...] Traveling salesman art Hierarchical exfoliation [...]