Querying Approximate Shortest Paths in Anisotropic Regions

We present a data structure for answering approximate shortest path queries in a planar subdivision from a fixed source. Let 0<=ρ<=1 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/ρ. Different convex distance functions may be used for different faces, and obstacles are allowed.

Let ε be any number strictly between 0 and 1. Our data structure returns a (1+ε) approximation of the shortest path cost from the fixed source to a query destination in O(log ρnε ) time. Afterwards, a (1 +ε)-approximate shortest path can be reported in O(log n) time plus the complexity of the path. The data structure uses O( ρ2n3ε2 log ρnε ) space and can be built in O( ρ2n3ε2 (log ρnε )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.

74216.pdf
PDF file

In  SIAM J. COMPUTING

Publisher  Society for Industrial and Applied Mathematics
Copyright © 2010 by Society for Industrial and Applied Mathematics.

Details

TypeArticle
Pages1888-1918
Volume39
Number5
> Publications > Querying Approximate Shortest Paths in Anisotropic Regions