Querying approximate shortest paths in anisotropic regions

We present a data structure for answering approximate shortest path queries ina planar subdivision from a fixed source. Let 1 be a real number.Distances in each face of this subdivision are measured by a possiblyasymmetric convex distance function whose unit disk is contained in aconcentric unit Euclidean disk, and contains a concentric Euclidean disk withradius 1/. Different convex distance functions may be used for differentfaces, and obstacles are allowed. Let be any number strictly between 0and 1. Our data structure returns a (1+)approximation of the shortest path cost from the fixed source to a querydestination in O(logn/) time. Afterwards, a(1+)-approximate shortest path can be reported in time linear in itscomplexity. The data structure uses O( ² n⁴/² log n/) space and can be built in O((² n⁴)/(²)(log n/)²) time. Our time and space bounds do not depend onany geometric parameter of the subdivision such as the minimum angle. Copyright 2007 ACM