Skip to main content
1 of 2
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Not an answer; just a request for clarification.


          [![Tours5][1]][1]
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$?

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

Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958