1
$\begingroup$

To me it seems possible, to successfully look at symmetric TSP instances from a geometry-point of view.

Examples are:

  • the diagonals of the convex hull of a set of points in the euclidean plane; those diagonals can't belong to the optimal tour through that points. As this is universally true for all planar euclidean TSP instances, there should be a deeper reason behind it, and, it is also universally true, that

  • in case of three collinear points, no optimal tour contains the edge connecting the two most distant points of such a triplet.

Another topic is to generalize geometric shapes to symmetric TSP-instances, e.g. how to define subtours with the "shape" of an euclidean circle or, to generalize the shape of planar quadrilaterals to subgraphs induced by 4 vertices (e.g. can the longest diagonal of a convex quadrilateral be part of the optimal tour?)

Questions:

  • is/was there any research going on in that direction (I'm aware of Linials paper "The geometry of graphs and some of its algorithmic applications", that is based on embedding graphs into euclidean spaces, but not what I am interested in)?

  • is anyone interested in that topic, which would also cover characterising geometric shapes by length-sums and comparisons alone?

  • is there already a proper term for coordinate-free, discrete "geometries", that are purely based on length-sums and their comparisons?

Any references or advice would be welcome.

(I was not sure about the proper tagging, so please fix if necessary).

$\endgroup$
5
  • $\begingroup$ Perhaps work on "the metric TSP" is close to your concerns? Here the only assumption is that the distances satisfy the triangle inequality, which captures your hull-diagonal and collinear-points examples. $\endgroup$ Jul 6, 2014 at 19:11
  • $\begingroup$ @JosephO'Rourke I am looking for results, that are valid for all symmetric TSP instances and, I have already succeeded in some questions. What I certainly don't want, is to "inject" terms (like angle or area) that require multiplication of weights. I am currently about to generalize the notion of convex hulls without making assumptions about the interrelation of the weights; its hard, but possible. $\endgroup$ Jul 6, 2014 at 19:20
  • $\begingroup$ @JosephO'Rourke I have already generalized the concept of the diagonals of the convex hull (cf e.g. "mathoverflow.net/questions/124093/…) without use of the triangle inequality; the collinearity generalizes to the notion of least detours, i.e. if an edge AB minimizes the detour over a vertex C, then AB is not in the optimal tour. $\endgroup$ Jul 6, 2014 at 19:27
  • $\begingroup$ OK, I see that my remark is not of much use, then. $\endgroup$ Jul 6, 2014 at 20:06
  • $\begingroup$ At least it helped to clarify, what I am looking for! $\endgroup$ Jul 6, 2014 at 20:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.