Approximation algorithms for Euclidean group TSP and TSP with neighborhoods

In the Euclidean traveling salesman problem with discrete neighborhoods, we are given a set of points P in the plane and a set of n connected regions (neighborhoods), each containing at least one point of P. We seek to find a tour of minimum length which visits at least one point in each region. We give (i) an O(α)-approximation algorithm for the case when the regions are disjoint and α-fat, with possibly varying size; (ii) an O(