  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}) +
\log\log({\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.
