The determination of time-dependent collision-free shortest paths has received a fair amount of attention. Here, we study the problem of computing a time-dependent shortest path among growing discs which has been previously studied for the instance where the departure times are fixed. We address a more general setting: For two given points $s$ and $d$, we wish to determine the function $mathcal{A}(t)$ which is the minimum arrival time at $d$ for any departure time $t$ at $s$. We present a $(1+epsilon)$-approximation algorithm for computing $mathcal{A}(t)$. As part of preprocessing, we execute $O({1 over epsilon} log({mathcal{V}_{r} over mathcal{V}_{c}}))$ shortest path computations for fixed departure times, where $mathcal{V}_{r}$ is the maximum speed of the robot and $mathcal{V}_{c}$ is the minimum growth rate of the discs. For any query departure time $t geq 0$ from $s$, we can approximate the minimum arrival time at the destination in $O(log ({1 over epsilon}) + loglog({mathcal{V}_{r} over mathcal{V}_{c}}))$ time, within a factor of $1+epsilon$ of optimal. Since we treat the shortest path computations as black-box functions, for different settings of growing discs, we can plug-in different shortest path algorithms. Thus, the exact time complexity of our algorithm is determined by the running time of the shortest path computations.
Download