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, Siu-Wing
Na, Hyeon-Suk
Vigneron, Antoine
Wang, Yajun
Issue Date 2008
Source SIAM journal on computing , v. 38, (3), 2008, p. 802-824
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 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
Files in this item:
File Description Size Format
weighted.pdf 311778 B Adobe PDF