# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Euclidean TSP in Narrow Strips

##### Fulltext (public)

arXiv:2003.09948.pdf

(Preprint), 2MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Alkema, H., de Berg, M., & Kisfaludi-Bak, S. (2020). Euclidean TSP in Narrow Strips. Retrieved from https://arxiv.org/abs/2003.09948.

Cite as: http://hdl.handle.net/21.11116/0000-0007-77A3-B

##### Abstract

We investigate how the complexity of Euclidean TSP for point sets $P$ inside
the strip $(-\infty,+\infty)\times [0,\delta]$ depends on the strip width
$\delta$. We obtain two main results. First, for the case where the points have
distinct integer $x$-coordinates, we prove that a shortest bitonic tour (which
can be computed in $O(n\log^2 n)$ time using an existing algorithm) is
guaranteed to be a shortest tour overall when $\delta\leq 2\sqrt{2}$, a bound
which is best possible. Second, we present an algorithm that is fixed-parameter
tractable with respect to $\delta$. More precisely, our algorithm has running
time $2^{O(\sqrt{\delta})} n^2$ for sparse point sets, where each
$1\times\delta$ 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]\times [0,\delta]$, it has an expected running time of
$2^{O(\sqrt{\delta})} n^2 + O(n^3)$.