2
$\begingroup$

Given $n$ non-overlapping circles of radius $1$ (i.e., the distance between the centers of any two circles is greater than $2$), how to find the minimum length path (the path can be of any form) that touches all the circles (we say that a path touches a circle if the minimum distance between a point of the path and the center of the circle is less or equal to $1$)? Or, how to find such good paths with small lengthes?

Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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. One of their algorithms 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

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ PTAS implies an approximation ratio arbitrarily close to 1. There is more than one algorithm in their paper, the PTAS algorithm is different from the 3.55 algorithm. $\endgroup$
    – Emil Jeřábek
    Commented Jul 8, 2014 at 12:48
  • $\begingroup$ @EmilJeřábek: I stand corrected---Thanks. (Altered the language to avoid misleading.) $\endgroup$
    – Joseph O'Rourke
    Commented Jul 8, 2014 at 12:50
  • $\begingroup$ @JosephO'Rourke. Thanks. But my problem is different from TSP with neighbor. I am looking for a path (that touches each circle) shorter than the path that connects the centers of each circles. $\endgroup$
    – lchen
    Commented Jul 8, 2014 at 13:39
  • $\begingroup$ I think if you look at the paper I cited, you will find your problem is not different. Don't be misled by Fig.1. $\endgroup$
    – Joseph O'Rourke
    Commented Jul 8, 2014 at 13:41
  • $\begingroup$ "For example, the neighborhoods may be disks centered at buyers’ locations, and the radius of each disk specifies the maximum distance a buyer is willing to travel to the meeting place." $\endgroup$
    – Joseph O'Rourke
    Commented Jul 8, 2014 at 13:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .