期刊
COMPUTER GRAPHICS FORUM
卷 40, 期 5, 页码 275-287出版社
WILEY
DOI: 10.1111/cgf.14373
关键词
CCS Concepts; center dot Mathematics of computing -> Paths and connectivity problems; Graph algorithms; center dot Theory of computation -> Routing and network design problems
The study focuses on the landmark distance function in a simply connected planar polygon, demonstrating the effectiveness of steepest descent in generating paths between any two points in the polygon without getting stuck.
We study the landmark distance function between two points in a simply connected planar polygon. We show that if the polygon vertices are used as landmarks, then the resulting landmark distance function to any given point in the polygon has a maximum principle and also does not contain local minima. The latter implies that a path between any two points in the polygon may be generated by steepest descent on this distance without getting stuck at a local minimum. Furthermore, if landmarks are increasingly added along polygon edges, the steepest descent path converges to the minimal geodesic path. Therefore, the landmark distance can be used, on the one hand in robotic navigation for routing autonomous agents along close-to-shortest paths and on the other for efficiently computing approximate geodesic distances between any two domain points, a property which may be useful in an extension of our work to surfaces in 3D. In the discrete setting, the steepest descent strategy becomes a greedy routing algorithm along the edges of a triangulation of the interior of the polygon, and our experiments indicate that this discrete landmark routing always delivers (i.e., does not get stuck) on nice triangulations.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据