Time-dependent shortest path queries among growing discs
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 (Formula presented.) shortest path computations for fixed departure times, where Vr is the maximum speed of the robot and Vc 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 (Formula presented.) 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.
|Conference||30th Canadian Conference on Computational Geometry, CCCG 2018|
Maheshwari, A, Nouri, A. (Arash), & Sack, J.-R. (2018). Time-dependent shortest path queries among growing discs. In Proceedings of the 30th Canadian Conference on Computational Geometry, CCCG 2018 (pp. 288–295).