Skip to main content
1 of 3
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

I believe you are seeking the optimal TSP disk tour, for congruent disks. This 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