Skip to main content
2 of 3
added 60 characters in body
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

I believe you are seeking the optimal TSP disk tour, for congruent disks, a special case of "TSP with neighborhoods." The TSP disk-tour problem is NP-hard, but there exists a PTAS (polynomial-time approximation scheme) for it. See the paper by Dumitrescu & Mitchell below. Their algorithm achieves an approximation ratio of $1 + 8/\pi \approx 3.55$, and is very efficient (although it would not be easy to implement).

Dumitrescu, Adrian, and Joseph SB Mitchell. "Approximation algorithms for TSP with neighborhoods in the plane." Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms (SODA). SIAM, 2001. (PDF download link)


      ![Fig.1][1]
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958