On Landmark Distances in Polygons

Simple item page
dc.contributor.authorGotsman, Craigen_US
dc.contributor.authorHormann, Kaien_US
dc.contributor.editorDigne, Julie and Crane, Keenanen_US
dc.date.accessioned2021-07-10T07:46:33Z
dc.date.available2021-07-10T07:46:33Z
dc.date.issued2021
dc.description.abstractWe 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.en_US
dc.description.number5
dc.description.sectionheadersDistances
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume40
dc.identifier.doi10.1111/cgf.14373
dc.identifier.issn1467-8659
dc.identifier.pages275-287
dc.identifier.urihttps://doi.org/10.1111/cgf.14373
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf14373
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectMathematics of computing
dc.subjectPaths and connectivity problems
dc.subjectGraph algorithms
dc.subjectTheory of computation
dc.subjectRouting and network design problems
dc.titleOn Landmark Distances in Polygonsen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
v40i5pp275-287.pdf
Size:
11.29 MB
Format:
Adobe Portable Document Format
Download
Collections
40-Issue 5