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, SiuWing
Na, HyeonSuk Vigneron, Antoine Wang, Yajun 


Issue Date  2010  
Source  SIAM Journal on Computing , v. 39, (5), 2010, p. 18881918  
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  00975397  
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 fulltext via DOI View fulltext via Web of Science View fulltext via Scopus Files in this item:
