1
$\begingroup$

This question was cross-posted to cstheory.SE here.

Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've developed a fleet of disposable delivery drones, each with an effective range of 50 kilometers. With this innovation, instead of travelling to each city to deliver your goods, you only need to fly your helicopter within 50km and let the drones finish the job.

Problem: How should your fly your helicopter to minimize travel distance?

More precisely, given a real number $R>0$ and $N$ distinct points $\{p_1, p_2, \ldots, p_N\}$ in the Euclidean plane, which path intersecting a closed disk of radius $R$ about each point minimizes total arc length? The path need not be closed and may intersect the disks in any order.

Clearly this problem reduces to TSP as $R \to 0$, so I don't expect to find an efficient exact algorithm. I would be satisfied to know what this problem is called in the literature and if efficient approximation algorithms are known.

Improve this question
$\endgroup$
5
  • $\begingroup$ Also posted on TCS.SE. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. $\endgroup$
    – D.W. ♦
    May 17, 2015 at 22:06
  • $\begingroup$ @D.W. Yes, I acknowledged this in the first line of the question. It is my understanding that such cross-posting is allowed if a question doesn't receive much response on a site. In my case I posted the question here, didn't get an answer in ~24 hrs, and tried again on CSTheory.SE. $\endgroup$
    – David Zhang
    May 17, 2015 at 22:37
  • $\begingroup$ Please read the link in my comment. If you read that link, you will learn that your understanding is faulty. Simultaneous cross-posting is not allowed, and waiting 24 hours is not sufficient (in fact, how long to wait is even mentioned already in my comment) -- I'm afraid you'll need to be more patient. $\endgroup$
    – D.W. ♦
    May 17, 2015 at 22:41
  • $\begingroup$ @D.W. I see. If this is a problem then by all means, flag this question for deletion. $\endgroup$
    – David Zhang
    May 17, 2015 at 22:45
  • $\begingroup$ I'm voting to close this question even though it is on-topic because it has been reposted on Theoretical Computer Science and answered there. $\endgroup$
    – Gilles 'SO- stop being evil'
    May 18, 2015 at 12:49

1 Answer 1

Reset to default
1
$\begingroup$

Huck Bennett has answered this question on cstheory.SE here.

This is a special case of the Travelling Salesman with Neighborhoods (TSPN) problem. In the general version, the neighborhoods need not all be the same.

A paper by Dumitrescu and Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, addresses your question. They give a constant factor approximation algorithm for a slightly more general problem (case 1), and a PTAS when the neighborhoods are disjoint balls of the same size (case 2).

As a side comment, I think Mitchell has done a lot of work on geometric TSP variants, so you might want to look at his other papers.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.