Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/3273
Approximate shortest paths in anisotropic regions
Authors  Cheng, SiuWing
Na, HyeonSuk Vigneron, Antoine Wang, Yajun 


Issue Date  2008  
Source  SIAM journal on computing , v. 38, (3), 2008, p. 802824  
Summary  Our goal is to find an approximate shortest path for a point robot moving in a planar subdivision with n vertices. Let rho >= 1 be a real number. Distances in each face of this subdivision are measured by a 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. These convex distance functions may be asymmetric. For any epsilon epsilon (0, 1) and for any two points upsilon(s) and upsilon(d), we give an algorithm that finds a path from upsilon(s) to upsilon(d) whose cost is at most (1 + epsilon) times the optimal. Our algorithm runs in O(rho(2) log rho/epsilon(2) n(3) log(rho n/epsilon)) time. This bound does not depend on any other parameters; in particular it does not depend on the minimum angle in the subdivision. We give applications to two special cases that have been considered before: the weighted region problem and motion planning in the presence of uniform flows. For the weighted region problem with weights in [1,rho] boolean OR {infinity}, the time bound of our algorithm improves to O(rho log rho/epsilon n(3) log(rho n/epsilon)).  
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:
