Journal
COMPUTER GRAPHICS FORUM
Volume 40, Issue 5, Pages 275-287Publisher
WILEY
DOI: 10.1111/cgf.14373
Keywords
CCS Concepts; center dot Mathematics of computing -> Paths and connectivity problems; Graph algorithms; center dot Theory of computation -> Routing and network design problems
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available