Euclidean TSP in Narrow Strips

Henk Alkema*, Mark de Berg, Remco van der Hofstad, Sándor Kisfaludi-Bak

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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) .

Original languageEnglish
Pages (from-to)1456-1506
Number of pages51
JournalDiscrete and Computational Geometry
Volume71
Issue number4
Early online date8 Jan 2024
DOIs
Publication statusE-pub ahead of print - 8 Jan 2024
MoE publication typeA1 Journal article-refereed

Keywords

  • Bitonic TSP
  • Computational geometry
  • Euclidean TSP
  • Fixed-parameter tractable algorithms

Fingerprint

Dive into the research topics of 'Euclidean TSP in Narrow Strips'. Together they form a unique fingerprint.

Cite this