# Dubins TSP crossing trajectory theorem

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.

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'$$.
• @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 – J. Schmidt Jul 9 at 15:54