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 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][1]][1] <br /> <sup>Optimal tour $62.5$ compared to $77.4$, greedy starting at $(8.6)$.</sup> Whereas every greedy tour of this set of points on an ellipse is also the TSP tour. [![Ellipse][2]][2] <br /> <sup>$|S|=18$.</sup> Perhaps the "local feature size" or the "reach of a manifold" can be used to quantify conditions on $S$? [1]: https://i.sstatic.net/jhSp1.jpg [2]: https://i.sstatic.net/nTEq4.jpg