Shortest-Path Queries in Geometric Networks

摘要

A Euclidean t-spanner for a point set V aS, a"?^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.