0
$\begingroup$

In the Dubins TSP (DTSP for short), one needs to visit a set of given points in the plane, and return to the starting point, minimizing the distance of such a trajectory. The difference with the Euclidean TSP (ETSP for short) however is that the visiting entity is curvature constrained by some $r$, meaning the vehicle can, at any moment in time, either go straight, or move on the edge of some circle of radius $r'\geq r$.

Consider the following theorem, by Le Ny et al. (Theorem 2 in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.982&rep=rep1&type=pdf) which we will call Theorem 1 in this post :

A trajectory based on an ETSP optimal visit order, is not necessarily an optimal trajectory for the DTSP.

(I changed the wording of their theorem to suit this post)

Suppose the next theorem, Theorem 2 :

There exists instances for which the optimal DTSP visit order creates a crossing ETSP trajectory.

My question is : Does Theorem 2 imply Theorem 1 ?
The idea is as follows. Since some instances have the optimal DTSP visit order creating a crossing ETSP trajectory $T$, this ETSP trajectory $T$ is not optimal (due to the triangle inequality). This in turn implies that some optimal ETSP trajectory $T*$ on these instances (or their corresponding optimal ETSP visit order) cannot be adapted and optimized to obtain the optimal DTSP trajectory. If it could, then $T = T*$, which is a contradiction, since $T$ admits a crossing trajectory.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

No, theorem 2 does not imply theorem 1 unless you also prove for that instance that every optimal DTSP visit order creates a crossing ETSP trajectory. There might be another optimal DTSP $|T'| = |T|$ visit order that does not result in a crossing ETSP so that we have $T* = T'$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ It is for this reason I used " THE optimal DTSP visit order " in Theorem 2, not just " an optimal DTSP visit order ". So, assuming there exists only one unique optimal DTSP visit order creating a crossing ETSP trajectory, Theorem 2 should imply Theorem 1 ? $\endgroup$
    – J. Schmidt
    Commented Jul 8, 2019 at 12:28
  • 1
    $\begingroup$ @J.Schmidt If it is unique, then yes. $\endgroup$
    – orlp
    Commented Jul 8, 2019 at 13:01
  • $\begingroup$ @orip You answered my question, but I would like to know also if Theorem 2 is considered "stronger" than Theorem 1 (again, assuming only one optimal DTSP visit order exists) $\endgroup$
    – J. Schmidt
    Commented Jul 9, 2019 at 9:55
  • $\begingroup$ @J.Schmidt Yes it's stronger under that assumption because it implies the other theorem but not the other way around. However I'm not convinced that the assumption holds at all. $\endgroup$
    – orlp
    Commented Jul 9, 2019 at 10:07
  • $\begingroup$ @orip I was thinking it holds for some dense points on the edge of two circles of radius $r$, gathered close to form an 8-like form (without the middle of the 8), i.e. something like this : imgur.com/ZUpreV0 $\endgroup$
    – J. Schmidt
    Commented Jul 9, 2019 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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