THE TRAVELING SALESMAN PROBLEM FOR LINES AND RAYS IN THE PLANE
Adrian Dumitrescu · Discrete Mathematics Algorithms and Applications · 2012
In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of n regions (neighborhoods) and we seek a shortest tour that visits each region. In the path variant, we seek a shortest path that visits each region. We present several linear-time approximation algorithms with improved ratios for these problems for two cases of neighborhoods that are (infinite) lines, and respectively, (half-infinite) rays. Along the way we derive a tight bound on the minimum perimeter of a rectangle enclosing an open curve of length L.