2
$\begingroup$

Consider a finite set of points $V \subseteq \mathbb{R}^2 $ as a TSP-instance under the standard $\| \cdot \|_2$ norm. (TSP stands for traveling salesman tour.) We know that every optimal TSP tour $T$ through $V$ must satisfy certain geometric properties, e.g.

  • No edges (that are not subsequent) of $T$ intersect each other (assuming not all points of $V$ lie on one single line).
  • The vertices on the boundary of $\mathrm{conv}(V)$ must be visited by $T$ according to their ordering on this boundary.

I'm very interested in what else is known about such geometric properties of optimal TSP tours. Any given references are highly appreciated.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
2
$\begingroup$

You must be careful with what you are actually asking for; the criteria you give as examples are valid for every simple polygon and do not characterize simple polygons of shortest perimeter with a given finite set of distinct points as the ends of its line segments.

There are ways fo detect edges that can't belong to the optimal tour, but I don't know about any criterion that identifies edges that must belong to the optimal tour. The example of the two crossing edges only says that not both can belong to the optimal tour, but not if any of them belongs to the optimal tour and which it would then be.

If additionally constraints on the location of the points are imposed then there is some hope: if the points are in convex configuration then and the tour doesn't have a pair of non-adjacent intersecting edges then the tour must be optimal.

Improve this answer
$\endgroup$
2
$\begingroup$

Here is a reference for edge elimination (identifying edges that cannot appear in an optimal tour): https://arxiv.org/abs/1402.7301

The techniques were motivated by Euclidean 2D distances but apply more generally.

Improve this answer
$\endgroup$

You must log in to answer this question.