New Approximation Algorithms for Touring Regions
| Autor: | Qi, Benjamin, Qi, Richard, Chen, Xinyang |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: to appear in SOCG 2023. V2 - fixed figures |
| Databáze: | arXiv |
| Externí odkaz: |
|