Euclidean TSP in Narrow Strips

We investigate how the complexity of Euclidean TSP for point sets P inside the strip (- ∞, + ∞) × [0 , δ] depends on the strip width δ . We obtain two main results. For the case where the points have distinct integer x-coordinates, we prove that a shortest bitonic tour (which can be computed in O(nlog ²n) time using an existing algorithm) is guaranteed to be a shortest tour overall when δ⩽22 , a bound which is best possible.We present an algorithm that is fixed-parameter tractable with respect to δ . Our algorithm has running time 2O(δ)n+O(δ2n2) for sparse point sets, where each 1 × δ rectangle inside the strip contains O(1) points. For random point sets, where the points are chosen uniformly at random from the rectangle [0 , n] × [0 , δ] , it has an expected running time of 2O(δ)n . These results generalise to point sets P inside a hypercylinder of width δ . In this case, the factors 2O(δ) become 2O(δ1-1/d) .