Traveling salesman problem of segments

In this paper, we present a polynomial time approximation scheme (PTAS) for a variant of the traveling salesman problem (called segment TSP) in which a traveling salesman tour is sought to traverse a set of n ε-separated segments in two dimensional space. Our results are based on a number of geometric observations and an interesting generalization of Arora's technique [5] for Euclidean TSP (of a set of points). The randomized version of our algorithm takes O(n²(log n)^O(1/ε4)) time to compute a (1 + ε)-approximation with probability ≥ 1/2, and can be derandomized with an additional factor of O(n²). Our technique is likely applicable to TSP problems of certain Jordan arcs and related problems.