摘要：A Euclidean t-spanner for a point set V âS, â"^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.
关键词：Shortest path; Euclidean spanner; data structure
