A PTAS for Euclidean Maximum Scatter TSP

We study the problem of finding a tour of $n$ points in $\mathbb{R}^d$ in which every edge is long. More precisely, we wish to find a tour that maximizes the length of the shortest edge in the tour. The problem is known as Maximum Scatter TSP, and it was introduced by Arkin et al. (SODA 1997), motivated by applications in manufacturing and medical imaging. Arkin et al. gave a $2$-approximation for the metric version of the problem and showed that this is the best possible ratio achievable in polynomial time (assuming $P \neq NP$). They raised the question of whether one can obtain a better approximation ratio in the planar Euclidean case. We answer this question in the affirmative in a more general setting, by giving a polynomial-time approximation scheme (PTAS) for Maximum Scatter TSP in an arbitrary fixed-dimensional Euclidean space.