Generating uniquely $k$-optimal point sets

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?

• 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 the optimal 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.

• You have never defined k-optimal. Do you mean a tour which is not optimal but can be improved by exchanging k edges, while exchanging fewer than k edges can never improve it? – Wolfgang May 16 '17 at 12:19
• 2@Wolfgang a tour is $k$-optimal, iff it can't be 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. – Manfred Weis May 16 '17 at 14:56
• OK, almost what I thought then. (modulo $k$ vs. $k+1$) So to get it straight: Joseph O'Rourke's 2nd tour is 1-optimal (if it doesn't matter that the orientation of the short edge in the circuit has changed), the 3rd one is 2-optimal. – Wolfgang May 16 '17 at 15:03
• @Wolfgang you put I right; I should have written "some simple polygons are $2$-optimal" because geometric intersection of a pair of non-adjacent edges requires the adjacent points to be in convex configuration. – Manfred Weis May 16 '17 at 17:54

Not an answer; just a request for clarification.

The points are not in convex position. The optimal tour is shown in the left figure.

(1) Is it "$k$-optimal" in your notation for some $k$? "Uniquely $k$-optimal"?

(2) The optimal tour cannot be improved. Do the two suboptimal tours each illustrate "exchanging $2$ edges"? Or $3$ edges? Or $6$?

• The optimal tour through $n$ points is always $n$-optimal; the thing about $k$-optimality is that the tour can't be improved, no matter which subset of $k$ edges is exchanged; that means, that for checking the next set $k$ edges, the previous change has to be reverted. A different aspect is however, that i suspect that in case of a unique $k$-optimal tour it is possible to find the overall optimal tour in $O(n^{k+1})$ time by repeatedly replacing non-optimal subsets of $k$ edges. – Manfred Weis Feb 20 '16 at 12:35
• the non-optimal tours in your examples correspond to exchanging $3$ edges of the optimal tour. – Manfred Weis Feb 20 '16 at 12:38
• @ManfredWeis: Thanks for those clarifications. – Joseph O'Rourke Feb 20 '16 at 12:52