This is the shortest-possible tour through 37,859 luminous stars within 3,000 parsecs from Earth. The data set was put together by galaxy map expert Kevin Jardine. The trip covers 2,823,545.3 parsecs.
The tour and mathematical proof that it's shortest possible were found with the LKH and Concorde solvers. Details of the computation are given on the compute page.
Click "Full View of Tour" in the top bar to fill the window with the tour drawing; the full view includes a sample from the piece "Crazy Charlie's Confession to America" by Maryland band Rick and the All-Stars.
Research team
• David Applegate, Google Research
• Robert Bixby, Gurobi Optimization and Rice University
• Vašek Chvátal, Charles University
• William Cook, University of Waterloo and Johns Hopkins University
• Daniel Espinoza, Google Inc.
• Marcos Goycoolea, Universidad Adolfo Ibanez
• Keld Helsgaun, Roskilde University
Notes
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 employed can be found on the TSP home page and on the LKH web site.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.