  We revisit the classic task of finding the shortest tour of $n$ points in
$d$-dimensional Euclidean space, for any fixed constant $d \geq 2$. We
determine the optimal dependence on $\varepsilon$ in the running time of an
algorithm that computes a $(1+\varepsilon)$-approximate tour, under a plausible
assumption. Specifically, we give an algorithm that runs in
$2^{O(1/\varepsilon^{d-1})} n\log n$ time. This improves the previously
smallest dependence on $\varepsilon$ in the running time
$(1/\varepsilon)^{O(1/\varepsilon^{d-1})}n \log n$ of the algorithm by Rao and
Smith (STOC 1998). We also show that a
$2^{o(1/\varepsilon^{d-1})}\mathrm{poly}(n)$ algorithm would violate the
Gap-Exponential Time Hypothesis (Gap-ETH).
  Our new algorithm builds upon the celebrated quadtree-based methods initially
proposed by Arora (J. ACM 1998), but it adds a new idea that we call
sparsity-sensitive patching. On a high level this lets the granularity with
which we simplify the tour depend on how sparse it is locally. We demonstrate
that our technique extends to other problems, by showing that for Steiner Tree
and Rectilinear Steiner Tree it yields the same running time. We complement our
results with a matching Gap-ETH lower bound for Rectilinear Steiner Tree.
