



















We consider distance queries in vertex-labeled planar graphs. For any fixed $0 < ε\leq 1/2$ we show how to preprocess a directed planar graph with vertex labels and arc lengths into a data structure that answers queries of the following form. Given a vertex $u$ and a label $λ$ return a $(1+ε)$-approximation of the distance from $u$ to its closest vertex with label $λ$. For a directed planar graph with $n$ vertices, such that the ratio of the largest to smallest arc length is bounded by $N$, the preprocessing time is $O(ε^{-2}n\lg^{3}{n}\lg(nN))$, the data structure size is $O(ε^{-1}n\lg{n}\lg(nN))$, and the query time is $O(\lg\lg{n}\lg\lg(nN) + ε^{-1})$. We also point out that a vertex label distance oracle for undirected planar graphs suggested in an earlier version of this paper is incorrect.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。