A PTAS for TSP with neighborhoods among fat regions in the plane

The Euclidean TSP with neighborhoods (TSPN) problem seeks a shortest tour that visits a given collection of n regions (neighborhoods). We present the first polynomial-time approximation scheme for TSPN for a set of regions given by arbitrary disjoint fat regions in the plane. This improves substantially upon the known approximation algorithms, and is the first PTAS for TSPN on regions of noncomparable sizes. Our result is based on a novel extension of the m-guillotine method. The result applies to regions that are "fat" in a very weak sense: each region P_i contains a disk of radius Ω(diam(P_i)), but is otherwise arbitrary. Further, the result applies even if the regions intersect arbitrarily, provided that there exists a packing of disjoint disks, of radii Ω(diam(P_i)), contained within their respective regions. Finally, the PTAS result applies also to the case in which the regions are sets of points or polygons, each each lying within one of a given set of disjoint fat regions.