2015/04/18 by Mozes, Shay, Skop, Eyal E.
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1504.04690
We consider distance queries in vertex-labeled planar graphs. For any fixed 0 < ε≤ 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(ε-2n\lg3n\lg(nN)), the data structure size is O(ε-1n\lgn\lg(nN)), and the query time is O(\lg\lgn\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.