3D Star TSPs


Using 3D astronomical data, we have created 12 instances of the TSP, ranging in size from 100 points up to 1.33 billion points. In these examples, star to star travel is measured by straight-line Euclidean distances in three-dimensional space, rounded to the nearest 1/10th parsec. (Why 3D?)

The tours we report come together with quality guarantees. For example, our tour through 2,079,471 stars, if not the absolute shortest possible, is off by at most a factor of 0.0000074. That is, we have a tour of length 28,884,352.4 parsecs and we know it's impossible to visit the stars in less than 28,884,139.0, a gap of only 213.4 parsecs.

Current results for the test instances are reported in the following table.

# of Stars Source Quality
100 HYG Optimal
1,000 DR1 + HYG Optimal
10,000 DR1 + HYG Optimal
37,859 K. Jardine Optimal
109,399 HYG Optimal
119,614 HYG Optimal
250,000 DR1 + HYG 0.0000043
2,079,471 DR1 + HYG 0.0000074
10,000,000 Gaia DR2 0.000032
100,000,000 Gaia DR2 0.00076
136,606,128 StarHorse In process
265,637,087 StarHorse In process
1,331,906,450 Gaia DR2 0.0038
References

The TSP point sets are based on David Nash's HYG Database and on Gaia distance estimates reported in the following three research papers.

Estimating distances from parallaxes. III. Distances of two million stars in the Gaia DR1 Catalogue
Tri L. Astraatmadija and Coryn A. L. Bailer-Jones
The Astrophysical Journal, Volume 833, Number 1 (2016).

Estimating distances from parallaxes. IV. Distances to 1.33 billion stars in Gaia data release 2
C.A.L. Bailer-Jones, J. Rybizki, M. Fouesneau, G. Mantelet, R. Andrae
The Astronomical Journal, Volume 156, Number 2 (2018).

Photo-astrometric distances, extinctions, and astrophysical parameters for Gaia DR2 stars brighter than G = 18
F. Anders et al.
Astronomy & Astrophysics, Volume 628, August 2019.

TSP 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

Information on the TSP solution techniques we have employed can be found on the TSP home page and on the LKH web site.

We thank Bob Vanderbei for pointing us to the HYG database. This was the start of our work on 3D star tours.

Computations were carried out on systems located at Roskilde University and at the University of Waterloo.

All tour images were 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 solutions.