We revisit the traveling salesman problem with neighborhoods (TSPN) and present the first constant-ratio approximation for disks in the plane: Given a set of n disks in the plane, a TSP tour whose length is at most O(1) times the optimal can be computed in time that is polynomial in n. Our result is the first constant-ratio approximation for a class of planar convex bodies of arbitrary size and arbitrary intersections. In order to achieve a O(1)-approximation, we reduce the traveling salesman problem with disks, up to constant factors, to a minimum weight hitting set problem in a geometric hypergraph. The connection between TSPN and hitting sets in geometric hypergraphs, established here, is likely to have future applications. Related work. Arkin and Hassin [2] gave constant-factor approximations for translates of a connected region, and more generally, for neighborhoods of pairwise parallel diameters, where the ratio between the longest and the shortest diameter is bounded by a constant. Dumitrescu and Mitchell [16] extended the above result to connected neighborhoods with comparable diameters. Bodlaender et al. [8] described a PTAS for TSPN with disjoint fat neighborhoods of about the same size in R d , where d is constant (this includes the case of disjoint unit disks in the plane). Earlier Dumitrescu and Mitchell [16] proposed a PTAS for TSPN with fat neighborhoods of about the same size and bounded depth in the plane, where Spirkl [42] recently reported and filled a gap; see also a follow-up note in [34]. Mata and Mitchell [28] gave a O(log n) approximation for TSPN with n connected and arbitrarily intersecting neighborhoods in the plane; see also [7]. Elbassioni et al. [19] and Gudmundsson and Levcopoulos [23] improved the running time of the algorithm. The O(log n)-approximation relies on the following early result by Levcopoulos and Lingas [27]: Every (simple) rectilinear polygon P with n vertices, r of which are reflex, can be partitioned in O(n log n) time into rectangles whose total perimeter is log r times the perimeter of P . Using an approximation algorithm due to Slavik [41] for Euclidean group TSP, de Berg et al. [6] obtained constant-factor approximations for disjoint fat convex regions (of arbitrary diameters) in the plane. Subsequently, Elbassioni et al. [19] gave constant-factor approximations for arbitrarily intersecting fat convex regions of comparable size. Preliminary work by Mitchell [32] gave a PTAS for planar regions of bounded depth and arbitrary size, in particular for disjoint fat regions. Chan and Jiang [12] gave a PTAS for fat, weakly disjoint regions in metric spaces of constant doubling dimension (combining an earlier QPTAS by Chan and Elbassioni [11] with a PTAS for TSP in doubling metrics by Bartal et al. [4]). Disks and balls are undoubtedly among the simplest neighborhood types [2, 16, 24] . TSPN for disks is NP-hard, and it remains so for congruent disks, since when the disk centers are fixed and the radius tends to zero, the problem reduces to TSP for points. Regarding approximations, the case of congruent balls is relatively well understood: Given a set of n congruent (say, unit) balls in R d , a TSP tour whose length is at most O(1) times the optimal can be computed in polynomial time, when d is constant [18] . However, for disks of arbitrary radii and intersections, no constantratio approximation was known. Some of the difficulties with disks of arbitrary radii in the plane where uncovered in [17] . Recent work of Dumitrescu and Tóth [18] focused on unbounded neighborhoods, such as lines or hyperplanes: They gave a constant-factor approximation for TSPN with n hyperplanes in R d in O(n) time; and a O(log 3 n)-approximation for n lines in R d in time polynomial in n, where d is constant. In contrast, the current paper considers TSPN with arbitrary disks in R 2 , which requires quite different approximation techniques and new ideas.
Then in REF a constant factor approximation was found that can handle arbitrary (possibly differently sized and intersecting) disks in the plane.
Constant-Factor Approximation for TSP with Disks
ArXiv
ArXiv
Mathematics Computer Science