Name
Abstract | ||
|---|---|---|
We consider the problem of computing shortest paths in three-dimensions in the presence of a single-obstacle polyhedral terrain, and present a new algorithm that for any p=1, computes a (c+@e)-approximation to the L"p-shortest path above a polyhedral terrain in O(n@elognloglogn) time and O(nlogn) space, where n is the number of vertices of the terrain, and c=2^(^p^-^1^)^/^p. This leads to a FPTAS for the problem in L"1 metric, a (2+@e)-factor approximation algorithm in Euclidean space, and a 2-approximation algorithm in the general L"p metric. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.ipl.2007.08.008 | Inf. Process. Lett. |
Keywords | Field | DocType |
p-shortest path,shortest path,2-approximation algorithm,single-obstacle polyhedral terrain,new algorithm,factor approximation algorithm,euclidean space,polyhedral terrain,general l,approximation algorithms,computational geometry,three dimensions | Approximation algorithm,Discrete mathematics,Combinatorics,Shortest path problem,Vertex (geometry),Terrain,Computational geometry,Euclidean space,Polyhedral terrain,Mathematics,Euclidean shortest path | Journal |
Volume | Issue | ISSN |
105 | 3 | 0020-0190 |
Citations | PageRank | References |
2 | 0.38 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hamid Zarrabi-Zadeh | 1 | 111 | 13.63 |