100 stars

This is the shortest-possible tour through the 3D locations of 100 nearby stars. The image of the tour is interactive. Go ahead and pinch, swipe, click, drag, and scroll to reveal its 3D structure.

Problems of this size are easy for the linear-programming, cutting-plane method: the 100-star tour and mathematical proof that it's shortest possible were found by the Concorde TSP solver in under half a second on my iMac.


For a guide to navigating the image, click the ⓘ button in the top right corner of the page.

Links to lots of information on the mathematical techniques we have employed can be found on the TSP home page.

Details on the point set for the star TSP instance are given on the Data page; further images can be found on the Tour page.

The tour is rendered with the three.js JavaScript 3D library.

We thank Michael Boyle for suggesting the use of color hue to indicate the order stars appear in our solution.