Querying approximate shortest paths in anisotropic regions
Résumé
We present a data structure for answering approximate shortest path queries in a planar subdivision from a fixed source. Let rhogeqslant1 be a real number. Distances in each face of this subdivision are measured by a possibly asymmetric convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius 1/rho. Different convex distance functions may be used for different faces, and obstacles are allowed. Let varepsilon be any number strictly between 0 and 1. Our data structure returns a (1+varepsilon) approximation of the shortest path cost from the fixed source to a query destination in O(logfracrhonvarepsilon) time. Afterwards, a (1+varepsilon)-approximate shortest path can be reported in O(logn) time plus the complexity of the path. The data structure uses $O(frac{rho^2n^3 {varepsilon^2}logfrac{rho n}{varepsilon})spaceandcanbebuiltinO(frac{rho^2n^3}{varepsilon^2}(logfrac{rho n}{varepsilon})^2)$ time. Our time and space bounds do not depend on any other parameter; in particular, they do not depend on any geometric parameter of the subdivision such as the minimum angle.