## 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 ^{2}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) .

Original language | English |
---|---|

Pages (from-to) | 1456-1506 |

Number of pages | 51 |

Journal | Discrete and Computational Geometry |

Volume | 71 |

Issue number | 4 |

Early online date | 8 Jan 2024 |

DOIs | |

Publication status | E-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.

Funders | Funder number |
---|---|

Nederlandse Organisatie voor Wetenschappelijk Onderzoek | NETWORKS-024.002.003 |

## Keywords

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