Query shortest paths amidst growing discs
Arash Nouri
Carleton University

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 speed at which the discs are growing is a polynomial function of degree $\beta$, (2) source and destination are given as query points. We show how to preprocess the growing discs so that, given two points $s$ and $d$, a query time-minimal path from $s$ to $d$ can be found in $O(n^2 \log (\beta n))$ time, where $n$ is the number of discs and where $\beta$ is the maximum degree of the polynomial speed functions. The expected 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^3 \beta^2)$.