Find all your DIY electronics in the MakerShed. 3D Printing, Kits, Arduino, Raspberry Pi, Books & more!

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.

penguins-211.png

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


Related
blog comments powered by Disqus

Featured Products from the MakerShed

Follow

Get every new post delivered to your Inbox.

Join 25,524 other followers