Euclidean TSP in Narrow Strips

Henk Alkema (Corresponding author), Mark de Berg, Remco van der Hofstad, Sándor Kisfaludi-Bak

Research output: Contribution to journalArticleAcademicpeer-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

Funding

This study was supported by Dutch Research council (NWO) under project no. NETWORKS-024.002.003. The work in this paper is supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003.

FundersFunder number
Nederlandse Organisatie voor Wetenschappelijk OnderzoekNETWORKS-024.002.003

    Keywords

    • Bitonic TSP
    • Computational geometry
    • Euclidean TSP
    • Fixed-parameter tractable algorithms
    • 68Q25
    • 68W40

    Fingerprint

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

    Cite this