Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/6556

Querying Approximate Shortest Paths in Anisotropic Regions

Authors Cheng, Siu-Wing
Na, Hyeon-Suk
Vigneron, Antoine
Wang, Yajun
Issue Date 2010
Source SIAM Journal on Computing, v. 39, (5), 2010, p. 1888-1918
Summary We present a data structure for answering approximate shortest path queries in a planar subdivision from a fixed source. Let rho >= 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/rho. Different convex distance functions may be used for different faces, and obstacles are allowed. Let e be any number strictly between 0 and 1. Our data structure returns a (1 + epsilon) approximation of the shortest path cost from the fixed source to a query destination in O(log rho n/epsilon) time. Afterwards, a (1 + epsilon)- approximate shortest path can be reported in O(log n) time plus the complexity of the path. The data structure uses O(rho(2)n(3)/epsilon(2) log rho n/epsilon) space and can be built in O(rho(2)n(3)/epsilon(2) (log rho n/epsilon)(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.
Subjects
ISSN 0097-5397
Rights Copyright © SIAM. This paper is made available with permission of the Society for Industrial and Applied Mathematics for limited noncommerical distribution only.
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Find@HKUST