|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/3273
|
| Title: | Approximate shortest paths in anisotropic regions |
| Authors: | Cheng, Siu-Wing
Na, Hyeon-Suk
Vigneron, Antoine
Wang, Yajun |
| Keywords: | Shortest path
Approximation algorithm
Computational geometry |
| Issue Date: | 2008 |
| Citation: | SIAM journal on computing, v.38, no. 3, p. 802-824 |
| Abstract: | Our goal is to find an approximate shortest path for a point robot moving in a planar subdivision with n vertices. Let ρ ≥ 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/ρ. Different convex distance functions may be used for different faces, and obstacles are allowed. These convex distance functions may be asymmetric. For any ε ∈ (0, 1) and for any two points vs and vd, we give an algorithm that finds a path from vs to vd whose cost is at most (1 + ε) times the optimal. Our algorithm runs in O (ρ2 log ρ/ε2 n3log (ρn/ε)) 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, ρ] ∪ {∞}, the time bound of our algorithm improves to O (ρ log ρ/ε n3log (ρn/ε)). |
| Rights: | Copyright © SIAM. This paper is made available with permission of the Society for Industrial and Applied Mathematics for limited noncommerical distribution only. |
| URI: | http://hdl.handle.net/1783.1/3273 |
| Appears in Collections: | CSE Journal/Magazine Articles
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| weighted.pdf | pre-published version | 304Kb | Adobe PDF | View/Open |
|
Find published version via |
All items in this Repository are protected by copyright, with all rights reserved.
|
