New Approximation Algorithms for Touring Regions

Abstract

We analyze the touring regions problem: find a ($1+\epsilon$)-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_1,R_2,R_3,\dots ,R_n$ in that order. Our main result is an $\mathcal{O}\left(\frac{n}{\sqrt{\epsilon }}\log \frac{1}{\epsilon }+\frac{1}{\epsilon }\right)$-time algorithm for touring disjoint disks. We also give an $\mathcal{O}\left(\min \left(\frac{n}{\epsilon },\frac{n^2}{\sqrt{\epsilon }}\right)\right)$-time algorithm for touring disjoint two-dimensional convex fat bodies. Both of these results naturally generalize to larger dimensions; we obtain $\mathcal{O}\left(\frac{n}{{\epsilon }^{d-1}}{\log }^2\frac{1}{\epsilon }+\frac{1}{{\epsilon }^{2d-2}}\right)$ and $\mathcal{O}\left(\frac{n}{{\epsilon }^{2d-2}}\right)$-time algorithms for touring disjoint $d$-dimensional balls and convex fat bodies, respectively.

to appear in SOCG 2023. V2 - fixed figures