New Approximation Algorithms for Touring Regions

2023/03/12 by Qi, Benjamin, Qi, Richard, Chen, Xinyang
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2303.06759

Abstract

We analyze the touring regions problem: find a (1+ε)-approximate Euclidean shortest path in d-dimensional space that starts at a given starting point, ends at a given ending point, and visits given regions R₁, R₂, R₃, …, R_n in that order. Our main result is an \mathcal O ((n)/(√ε)log\frac1ε + \frac1ε )-time algorithm for touring disjoint disks. We also give an \mathcal O (min(\fracnε, (n²)/(√ ε)) )-time algorithm for touring disjoint two-dimensional convex fat bodies. Both of these results naturally generalize to larger dimensions; we obtain \mathcal O(\fracnε^d-1log²\frac1ε+\frac1ε^2d-2) and \mathcal O(\fracnε^2d-2)-time algorithms for touring disjoint d-dimensional balls and convex fat bodies, respectively.

Related

• A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
• Computing shortest paths amid non-overlapping weighted disks
• Euclidean TSP with few inner points in linear space
• A PTAS for TSP with Neighborhoods Among Fat Regions in the Plane
• The traveling salesman problem for lines, balls and planes