In this paper we study the quickest path problem where speed is direction-dependent (anisotropic). The problem arises in sailing, robotics, aircraft navigation, and routing of autonomous vehicles, where the speed is affected by the direction of waves, winds or slope of the terrain. We present an approximation algorithm to find a quickest path for a point robot moving in planar subdivision, where each face is assigned a translational flow that reflects the cost of travelling within this face. Our main contribution is a data structure that given a subdivision with translational flows returns a (1+e)-approximate quickest path in the subdivision between any two query points in the plane.
Quickest Paths in Anisotropic Media
2011
15 Seiten
Aufsatz (Konferenz)
Englisch
Quickest Paths in a Dynamic Network: A Faster Algorithm
British Library Conference Proceedings | 2002
|Galveston -- Port of quickest dispatch
Engineering Index Backfile | 1950
Ford Mustang - Quickest ever pony car
Online Contents | 1999