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 an interesting combinatorial result which bounds the total number of entry points in an optimal TSP tour and a generalization of Arora's technique⁵ for Euclidean TSP (of a set of points). The randomized version of our algorithm takes O(n ²(log_n)O^(1/∈2)) time to compute a (1 + ∈)-approximation with probability ≥ 1/2, and can be derandomized with an additional factor of O(n²).