1
$\begingroup$

Define a greedy tour of a set $S=\{p_1,\ldots,p_n\}$ of $n$ points in $\mathbb{R}^2$ as produced by selecting the $i$-th point $p_i$ to start, and then connecting to the nearest neighbor $p_j$ to $p_i$, then to the nearest neighbor to $p_j$ (excluding $p_i$), and so on, finally closing back to the start $p_i$. So there are $n$ possible greedy tours. Assume general position so there are no ties.

My question is:

When is the shortest greedy tour equal to the Euclidean TSP? Is there any characterization, or at least sufficient conditions on $S$, such that the shortest greedy tour is the TSP?

For example, below shows the optimal TSP for a $50$-point set, and one of the $50$ greedy tours that fails to achieve the TSP.

   50 pts
   Optimal tour $62.5$ compared to $77.4$, greedy starting at $(8.6)$.

Whereas every greedy tour of this set of points on an ellipse is also the TSP tour.

   Ellipse
   $|S|=18$.

Perhaps the "local feature size" or the "reach of a manifold" can be used to quantify conditions on $S$?

$\endgroup$
4
  • 2
    $\begingroup$ See en.wikipedia.org/wiki/… for some discussion of the nearest neighbor approach to TSP. (Note that the minimum spanning tree-based algorithm is also quite simple, but does better.) $\endgroup$ Commented Feb 11, 2022 at 23:58
  • $\begingroup$ Thanks, @SamHopkins. I am less interested in the algorithmic issues as I am in understanding the shape of the point sets that can be greedily TSP'ed, so-to-speak. $\endgroup$ Commented Feb 12, 2022 at 0:23
  • 1
    $\begingroup$ Yeah, I get that, was just a comment. My (random) guess would be that it would be hard to describe the TSP instances where nearest neighbor is optimal. $\endgroup$ Commented Feb 12, 2022 at 0:24
  • 1
    $\begingroup$ any set of points that samples a piecewise smooth closed curve dense enough will do where *dense enough" means that the Euclidean distance between neighboring points is e.g. smaller then the minimum distance betwen a point of the curve's Voronoi diagram to a point on the curve. Actually twice that distance may suffice. $\endgroup$ Commented Feb 21, 2022 at 4:20

1 Answer 1

1
$\begingroup$

A simple "a posteriori" criterion is that on the optimal tour the distances to the tour-neighbors is smaller than that to any of the other vertices.
Convexity alone doesn't suffice as the example of ellipses with sufficiently high excentricity demonstrates.

Another, "a priory" criterion may be that the maximum weight matching of every $K_4$ induced by 4 vertices of the TSP instance consists of the two longest edges of that subgraph.

Ruminating further, a general sufficient condition is that the Minimum Spanning Tree is linear and the edge joining the leaf nodes doesn't cross a tree edge.

The simplest sufficient and generally applicable criterion is however that the set of edges that is the union of the two shortest edges, that are adjacent to a vertex, constitutes to a tour.

Edit
there are counter examples to the criteria tha I have deleted: the instance with points $(0,0),\,(0,1),\,(1,1),\,(1,0),(1/k,1),\,\cdots,\,((k-1)/k,1)$

$\endgroup$
1
  • $\begingroup$ Thanks for thinking about my question. The MST condition is natural. Not sure about the $K_4$ idea. $\endgroup$ Commented Feb 19, 2022 at 16:35

You must log in to answer this question.

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