3
$\begingroup$

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 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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Wolfgang
    Commented May 16, 2017 at 12:19
  • $\begingroup$ 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. $\endgroup$
    – Manfred Weis
    Commented May 16, 2017 at 14:56
  • $\begingroup$ 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. $\endgroup$
    – Wolfgang
    Commented May 16, 2017 at 15:03
  • $\begingroup$ @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. $\endgroup$
    – Manfred Weis
    Commented May 16, 2017 at 17:54

1 Answer 1

Reset to default
0
$\begingroup$

Not an answer; just a request for clarification.

          Tours5
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$?

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Manfred Weis
    Commented Feb 20, 2016 at 12:35
  • $\begingroup$ the non-optimal tours in your examples correspond to exchanging $3$ edges of the optimal tour. $\endgroup$
    – Manfred Weis
    Commented Feb 20, 2016 at 12:38
  • $\begingroup$ @ManfredWeis: Thanks for those clarifications. $\endgroup$
    – Joseph O'Rourke
    Commented Feb 20, 2016 at 12:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .