4
$\begingroup$

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.

Question:

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.

Improve this question
$\endgroup$
4
  • $\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
    Commented Sep 15, 2017 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
    Commented Sep 16, 2017 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
    Commented Sep 16, 2017 at 8:39
  • $\begingroup$ All points or cities shall be distinct, with a positive, finite real distance between each pair. $\endgroup$
    – Manfred Weis
    Commented Sep 16, 2017 at 10:36

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice counter example! That helps me in the correct formulation of TSP heuristic. $\endgroup$
    – Manfred Weis
    Commented Sep 16, 2017 at 15:49

You must log in to answer this question.

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