The convex-hull-and-k-lineTravelling Salesman Problem

We present a polynomial time solution algorithm for the so-called Convex-hull-and-k-line TSP: This is a special case of the Euclidean TSP where 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 that the carrying lines of all these segments intersect the hull in two common edges. Our result contains and generalizes three earlier results that are due to Cutler (1980), to Rote (1992), and to Deineko, Van Dal and Rote (1994).