MS Defense: Well-Separation Heuristics for the Metric Traveling Salesman Problem

Well-separated pair decompositions (WSPDs) are a fundamental tool in computational geometry and underlie many geometric approximation algorithms. Despite their widespread use, comparatively little is known about how well-separation constrains the structure of tours in the metric Traveling Salesman Problem (TSP).
In this work, we investigate the relationship between WSPDs and TSP tours, providing new insights into how well-separation can be leveraged to design efficient heuristics for the metric TSP. Our main results revolve around proving that if a point set can be partitioned into two well-separated sets, then any optimal TSP tour must visit the points in each set consecutively. We then extend this result to the various cases of the multiple Traveling Salesman Problem (mTSP) where we show that similar results hold for different configurations of endpoints. Furthermore, we develop efficient algorithms for testing whether a given point set can be partitioned into well-separated sets, and how to leverage such a partitioning to efficiently compute optimal TSP tours. Finally, we discuss the relevance of these results by observing the existence of TSPLIB instances that can be partitioned into well-separated sets. We further determine that when randomly generating point sets down to a separation factor of s≈0.5, the problems still obey the results of the theorem that were proved for tighter bounds.