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.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Quickest Paths in Anisotropic Media


    Beteiligte:


    Erscheinungsdatum :

    2011


    Format / Umfang :

    15 Seiten





    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Print


    Sprache :

    Englisch




    Quickest Paths in a Dynamic Network: A Faster Algorithm

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


    Galveston -- Port of quickest dispatch

    Engineering Index Backfile | 1950



    Asymptotically Optimum Sample Size for Quickest Detection

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