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.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Quickest Paths in Anisotropic Media


    Contributors:


    Publication date :

    2011


    Size :

    15 Seiten





    Type of media :

    Conference paper


    Type of material :

    Print


    Language :

    English




    Quickest Paths in a Dynamic Network: A Faster Algorithm

    Dial, R. B. / American Society of Civil Engineers | British Library Conference Proceedings | 2002


    Quickest Cluster Flow Problems

    Hamacher, H.W. / Leiner, K. / Ruzika, S. | British Library Conference Proceedings | 2011


    Galveston -- Port of quickest dispatch

    Engineering Index Backfile | 1950


    Asymptotically Optimum Sample Size for Quickest Detection

    Pelkowitz, L. / Schwarts, S.C. | IEEE | 1987