Querying Approximate Shortest Paths in Anisotropic Regions

Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang

2010

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.

PDF file |

In SIAM J. COMPUTING

Publisher Society for Industrial and Applied Mathematics

Copyright © 2010 by Society for Industrial and Applied Mathematics.

Type | Article |

Pages | 1888-1918 |

Volume | 39 |

Number | 5 |

> Publications > Querying Approximate Shortest Paths in Anisotropic Regions