Query Shortest Paths Amidst Growing Discs
share
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 , 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 ( n)) time. The preprocessing time of our algorithm is O(n^2 n + k 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 ∈ O(n^3).
READ FULL TEXT