Approximating Time-Dependent Shortest Path Among Growing Discs
We study time-dependent collision free shortest path among growing discs. For two given points $s$ and $d$, let function $A_{s,d}(t)$ return the minimum arrival time at $d$ for any departure time $t$ at $s$. We present a $(1+\epsilon)$-approximation for the minimum arrival time function $A_{s,d}(t)$. Our algorithm runs $O(\mu + {1 \over \epsilon} \log({V_r \over V_m}))$ time minimal path computations for fixed departure times, where $\mu$ is the total number of intersections between the tangent lines and the discs, $V_r$ is the maximum speed of the robot and $V_m$ is the minimum growth rate of the discs.