This question is motivated by the observation that finding an optimal tour through a set of points in the Euclidean plane is especially simple, if the points are in convex configuration and, that the relative order of the points on the convex hull is preserved in the optimal tour through arbitrary finite sets of points in the Euclidean plane.

After some thinking about those observations, I suspect that the reason why shortest tours through points in convex configuration are so easy to find, is owed to the fact that for those point sets the tour without geometric intersection of edges is unique, whereas in more general configurations several simple polygons exist.

My idea for generalizing the notion of being in convex configuration to the vertices of weighted symmetric graphs was to to define the vertices to be in $k$-*convex configuration* if there is exactly one tour that can't be improved by exchanging $k$ or fewer edges (i.e. via the uniqueness of the k-optimal tour).

Questions:

What are examples of point sets, that are not in geometrically convex configuration and have a unique $k$-optimal tour, but no unique $h$-optimal tour for $h<k$?

How can such point sets be efficiently generated for a given value of $k$?

How can the uniqueness of a $k$-optimal tour through a point set be verified?

Does the uniqueness of a $k$-optimal tour imply that it also is

theoptimal tour through the point set (which I suspect to be true)?

In reply to the comments, I would like to remark, that my notion of $k$-optimality agrees with the one on slide 16 of this presentation.

can'tbe improved by exchanging $k$ or fewer edges or, put differently: any better tour has at least $k+1$ different edges. Simple polygons are $2$-optimal, but polygons with intersecting pairs of non-adjacent edges are $1$-optimal because they can be improved by exchanging a pair of crossing edges. I think the term "$k$-optimal was coined by Lin and/or Kernighan, but I have to look that up. $\endgroup$ – Manfred Weis May 16 '17 at 14:56