THE CONVEX-HULL-AND-K-LINE TRAVELING SALESMAN PROBLEM

We present a polynomial time solution algorithm for the so-called Conv ex-hull-and-k-line TSP: This is a special case of the Euclidean TSP wh ere n - m of the cities lie on the convex hull and m of the cities lie on k almost parallel line segments in the interior of the hull such t hat the carrying lines of all these segments intersect the hull in two common edges. Our result contains and generalizes three earlier resul ts that are due to Cutler (1980),to Rote (1992), and to Deineko, Van D al and Rote (1994).