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
Conference paper
English
Quickest Paths in a Dynamic Network: A Faster Algorithm
British Library Conference Proceedings | 2002
|Quickest Cluster Flow Problems
British Library Conference Proceedings | 2011
|Galveston -- Port of quickest dispatch
Engineering Index Backfile | 1950
Quickest Detection for Sequential Decentralized Decision Systems
Online Contents | 1996
|