Quickest paths in anisotropic media

Radwa El Shawi, Joachim Gudmundsson

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

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 + ε)-approximate quickest path in the subdivision between any two query points in the plane.

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings
Pages247-261
Number of pages15
DOIs
Publication statusPublished - 29 Aug 2011
Event5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011 - Zhangjiajie, China
Duration: 4 Aug 20116 Aug 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6831 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011
CountryChina
CityZhangjiajie
Period4/08/116/08/11

Fingerprint

Anisotropic media
Anisotropic Media
Subdivision
Path
Approximation algorithms
Face
Data structures
Navigation
Robotics
Autonomous Vehicles
Aircraft
Robots
Approximation Algorithms
Slope
Data Structures
Routing
Robot
Query
Costs
Dependent

Cite this

El Shawi, R., & Gudmundsson, J. (2011). Quickest paths in anisotropic media. In Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings (pp. 247-261). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6831 LNCS). https://doi.org/10.1007/978-3-642-22616-8_20
El Shawi, Radwa ; Gudmundsson, Joachim. / Quickest paths in anisotropic media. Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings. 2011. pp. 247-261 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{9815b6b75eae4cb782b8f24139809505,
title = "Quickest paths in anisotropic media",
abstract = "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 + ε)-approximate quickest path in the subdivision between any two query points in the plane.",
author = "{El Shawi}, Radwa and Joachim Gudmundsson",
year = "2011",
month = "8",
day = "29",
doi = "10.1007/978-3-642-22616-8_20",
language = "English",
isbn = "9783642226151",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "247--261",
booktitle = "Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings",

}

El Shawi, R & Gudmundsson, J 2011, Quickest paths in anisotropic media. in Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6831 LNCS, pp. 247-261, 5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011, Zhangjiajie, China, 4/08/11. https://doi.org/10.1007/978-3-642-22616-8_20

Quickest paths in anisotropic media. / El Shawi, Radwa; Gudmundsson, Joachim.

Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings. 2011. p. 247-261 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6831 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

T1 - Quickest paths in anisotropic media

AU - El Shawi, Radwa

AU - Gudmundsson, Joachim

PY - 2011/8/29

Y1 - 2011/8/29

N2 - 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 + ε)-approximate quickest path in the subdivision between any two query points in the plane.

AB - 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 + ε)-approximate quickest path in the subdivision between any two query points in the plane.

UR - http://www.scopus.com/inward/record.url?scp=80051991036&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-22616-8_20

DO - 10.1007/978-3-642-22616-8_20

M3 - Conference contribution

SN - 9783642226151

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 247

EP - 261

BT - Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings

ER -

El Shawi R, Gudmundsson J. Quickest paths in anisotropic media. In Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings. 2011. p. 247-261. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-22616-8_20