The determination of collision-free shortest paths among growing discs has previously been studied for discs with fixed growing rates. Here, we study a more general case of this problem, where: (1) the speeds at which the discs are growing are polynomial functions of degree $dd$, and (2) the source and destination points are given as query points. We show how to preprocess the $n$ growing discs so that, for two given query points $s$ and $d$, a shortest path from $s$ to $d$ can be found in $O(n^2 log (dd n))$ time. The preprocessing time of our algorithm is $O(n^2 log n + k log k)$ where $k$ is the number of intersections between the growing discs and the tangent paths (straight line paths which touch the boundaries of two growing discs). We also prove that $k in O(n^3dd)$.
Download