Near optimal algorithm for the shortest descending path on the surface of a convex terrain

详细信息	查看全文 | 推荐本文 |

• 作者：Sasanka Roy¹ ; ^{sasanka.ro@gmail.com}
• 关键词：Shortest path ; Terrain ; Geodesic path ; Computational geometry
• 刊名：Journal of Discrete Algorithms
• 出版年：2012
• 期刊代码：10_15708667
• 类别：mt
• 出版时间：August, 2012
• 卷：15
• 期：Complete
• 页码：63-70
• 文件大小：216 K

摘要

We study the problem of finding a shortest descending path (SDP) between a pair of points, called source (s) and destination (t), on the surface of a triangulated convex terrain with n faces. A path from s to t on a polyhedral terrain is descending if the height of a point p never increases while we move p along the path from s to t. Time and space complexity requirement of our algorithm are and , respectively. Here and are time and space complexity requirement for finding shortest geodesic path (SGP) between a pair of points on the surface of a convex polyhedra. The best known bounds on and are both due to Schreiber and Sharir (2008) . Earlier best known time and space complexity results of SDP on convex terrain were and , respectively, and appears in Roy et al. (2007) . Thus our algorithm improves both time and space complexity requirement of SDP problem by almost a linear factor over earlier best known results.