10,000 stars

This is the shortest-possible tour through 10,000 points in 3D. These are the locations of the nearest 10,000 stars in the Gaia DR1 data set. The tour and mathematical proof that it is shortest possible were found with the Concorde TSP solver. The computation time was a little under 27 minutes on an iMac with a 4.2 GHz Intel Core i7 processor.

Click "Full View of Tour" in the top bar to fill the window with the tour drawing; the full view includes a piano piece composed by Dan Naiman, specially for the Star TSP tours.


For a guide to navigating the moving 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.