TY - JOUR

T1 - Euclidean TSP in Narrow Strips

AU - Alkema, Henk

AU - de Berg, Mark

AU - van der Hofstad, Remco

AU - Kisfaludi-Bak, Sándor

N1 - Funding Information:
This study was supported by Dutch Research council (NWO) under project no. NETWORKS-024.002.003.
Funding Information:
The work in this paper is supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003.
Publisher Copyright:
© 2024, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2024/6

Y1 - 2024/6

N2 - 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 2n) 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) .

AB - 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 2n) 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) .

KW - Bitonic TSP

KW - Computational geometry

KW - Euclidean TSP

KW - Fixed-parameter tractable algorithms

UR - http://www.scopus.com/inward/record.url?scp=85181706363&partnerID=8YFLogxK

U2 - 10.1007/s00454-023-00609-7

DO - 10.1007/s00454-023-00609-7

M3 - Article

AN - SCOPUS:85181706363

SN - 0179-5376

VL - 71

SP - 1456

EP - 1506

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 4

ER -