Traveling Salesman Problem Art

Podcast Episode Summary

Craig Kaplan and Robert Bosch turned the Traveling Salesman Problem - a famous and important problem from computer science - in to a way of rendering halftone images, called TSP Art.

The goal of the Travelling Salesman Problem (TSP) is, given a list of cities, to determine the shortest tour that visits each city exactly once. The ability to solve this problem is important in a variety of fields, from logistics planning to electronics to DNA sequencing. Kaplan and Bosch generate "cities" with a density proportional to the density of an image and then apply the TSP. Two properties of the approximate solution they find make this visualization work -- first, the density of the routing tends to mirror the density of the cities (and thus the density of the original picture), and second, the path never crosses itself (which gives the result a unique look).

TSP Art: short version or the full paper (pdf).

via hacker news