Shortest-Path Queries in Geometric Networks
Eunjin Oh · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2020
A Euclidean t-spanner for a point set V ⊂ ℝ^d is a graph such that, for any two points p and q in V, the distance between p and q in the graph is at most t times the Euclidean distance between p and q. Gudmundsson et al. [TALG 2008] presented a data structure for answering ε-approximate distance queries in a Euclidean spanner in constant time, but it seems unlikely that one can report the path itself using this data structure. In this paper, we present a data structure of size O(nlog n) that answers ε-approximate shortest-path queries in time linear in the size of the output.