New Approximation Algorithms for Touring Regions

03/12/2023

∙

by   Benjamin Qi, et al.

∙

0

∙

share

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_1, R_2, R_3, …, R_n in that order. Our main result is an 𝒪(n/√(ϵ)log1/ϵ + 1/ϵ)-time algorithm for touring disjoint disks. We also give an 𝒪 (min(n/ϵ, n^2/√(ϵ)) )-time algorithm for touring disjoint two-dimensional convex fat bodies. Both of these results naturally generalize to larger dimensions; we obtain 𝒪(n/ϵ^d-1log^21/ϵ+1/ϵ^2d-2) and 𝒪(n/ϵ^2d-2)-time algorithms for touring disjoint d-dimensional balls and convex fat bodies, respectively.