Abstract | ||
---|---|---|
We consider the problem of path planning above a polyhedral terrain and present a new algorithm that for any p >= 1, computes a (c + epsilon)-approximation to the L-p-shortest path above a polyhedral terrain in O(n/epsilon log n log log n) time and O(n log n) space, where n. is the number of vertices of the terrain, and c = 2((p-1)/p). This leads to an E-approximation algorithm for the problem in L-1 metric, and a (root 2 + epsilon)-factor approximation algorithm in Euclidean space. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1109/ROBOT.2006.1641819 | 2006 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION (ICRA), VOLS 1-10 |
Keywords | DocType | Volume |
computational complexity,approximation theory,euclidean space,robots,approximation algorithm,path planning,computer science,shortest path,shortest path problem,motion planning,approximation algorithms,euclidean distance | Conference | 2006 |
Issue | ISSN | Citations |
1 | 1050-4729 | 0 |
PageRank | References | Authors |
0.34 | 7 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hamid Zarrabi-Zadeh | 1 | 111 | 13.63 |