Time-Dependent Shortest Path Queries Among Growing Discs
share
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 A(t) which is the minimum arrival time at d for any departure time t at s. We present a (1+ϵ)-approximation algorithm for computing A(t). As part of preprocessing, we execute O(1 ϵ(V_rV_c)) shortest path computations for fixed departure times, where V_r is the maximum speed of the robot and V_c is the minimum growth rate of the discs. For any query departure time t ≥ 0 from s, we can approximate the minimum arrival time at the destination in O( (1 ϵ) + (V_rV_c)) time, within a factor of 1+ϵ 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.
READ FULL TEXT