# Time-Dependent Shortest Path Queries Among Growing Discs

Preprint · Anil Maheshwari, Arash Nouri, Jörg-Rüdiger Sack

- Archive id: arxiv:1808.01984
- Published: 2018-08-06
- arXiv: https://arxiv.org/abs/1808.01984
- Source URL: https://arxiv.org/abs/1808.01984
- PDF: https://arxiv.org/pdf/1808.01984
- Provenance: arxiv

## Abstract

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 $\\mathcal{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 $\\mathcal{A}(t)$. As part of preprocessing, we execute $O({1 \\over ε} \\log({\\mathcal{V}\_{r} \\over \\mathcal{V}\_{c}}))$ shortest path computations for fixed departure times, where $\\mathcal{V}\_{r}$ is the maximum speed of the robot and $\\mathcal{V}\_{c}$ is the minimum growth rate of the discs. For any query departure time $t \\geq 0$ from $s$, we can approximate the minimum arrival time at the destination in $O(\\log ({1 \\over ε}) + \\log\\log({\\mathcal{V}\_{r} \\over \\mathcal{V}\_{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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.