let $\mathcal{P}$ be a finite set of points in the euclidean plane in general position, and let $$\lbrace p_A,p_B,p_C,p_D\rbrace: \ \|p_C-p_A\|+\|p_D-p_B\|\ \gt \|p_i-p_h\|+\|p_k-p_j\|\quad\forall\ \mathcal{P}\supset\lbrace h,i,j,k\rbrace\ne\lbrace A,B,C,D\rbrace\subset\mathcal{P}$$ be the quadrilateral with the maximal induced maximum weight perfect matching.


Is it possible, that $\left( p_A,p_C\right)$ or $\left(p_B,p_D\right)$ is contained in the shortest tour through the points of $\mathcal{P}$?

I am convinced, that such a shortest tour can't exist, but don't know, how to go about proving that; therefore I am hoping for a proof proving or disproving the existence of such optimal tours.

  • $\begingroup$ May you clarify? It is unclear whether (i) a route is supposed to be closed (=cyclic) or not, (ii) $\{\dots\}$ is a set or an ordered tuple, (iii) elements of $\{\dots\} may repeat or not... $\endgroup$ – Ilya Bogdanov Sep 15 '17 at 18:00
  • $\begingroup$ Tours are round trips, where every city, resp. point is visited exactly once and the road, resp. edge, via which a city is entered, is different from the one via which it is left. So the sequence, in which the cities are visited, corresponds to a permutation with a single cycle. $\endgroup$ – Manfred Weis Sep 16 '17 at 6:57
  • $\begingroup$ What about the other ambiguities? Do you thin that $\{A,D,B,C\}=\{A,B,C,D\}$ or not? Do you allow $A=B$? $\endgroup$ – Ilya Bogdanov Sep 16 '17 at 8:39
  • $\begingroup$ All points or cities shall be distinct, with a positive, finite real distance between each pair. $\endgroup$ – Manfred Weis Sep 16 '17 at 10:36

I assume that I interpret the question correctly (I fainled in getting a proper response...).

In the left figure below you see a degenerate (almost-)counterexample: the tour $BACDEB$ is the (unique) shortest one (because a tour cannot be shorter than the perimeter of $BDE$). The only trouble is that there are two pairs of edges (having no common vertices) with the maximal sum of lengths, namely $AC,BD$ and $AD,BC$ (all other distances are hopelessly shorter). This can be cured by modifying the picture a bit, replacing the line segment $BACD$ by a thin parallelogram $ABCD$, as shown in the right figure.

A degenerate and a non-degenerate examples

  • $\begingroup$ Nice counter example! That helps me in the correct formulation of TSP heuristic. $\endgroup$ – Manfred Weis Sep 16 '17 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.