Skip to main content
3 of 3
copied abbreviation to body
YCor
  • 63.9k
  • 5
  • 187
  • 285

References for geometric properties of optimal Euclidean traveling salesman tour

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.