Euclidean TSP in Narrow Strips

Henk Alkema, Mark de Berg, Remco van der Hofstad +1

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. F…