New Approximation Algorithms for Touring Regions
| Autor: | Qi, Benjamin, Qi, Richard |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: | |
| DOI: | 10.4230/lipics.socg.2023.54 |
| Popis: | 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 O (n/√ε log{1/ε} + 1/ε)-time algorithm for touring disjoint disks. We also give an O(min(n/ε, n²/√ε))-time algorithm for touring disjoint two-dimensional convex fat bodies. Both of these results naturally generalize to larger dimensions; we obtain O(n/{ε^{d-1}} log²1/ε + 1/ε^{2d-2}) and O(n/ε^{2d-2})-time algorithms for touring disjoint d-dimensional balls and convex fat bodies, respectively. LIPIcs, Vol. 258, 39th International Symposium on Computational Geometry (SoCG 2023), pages 54:1-54:16 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|