Quickest path queries on transportation network

Radwa El Shawi, Joachim Gudmundsson, Christos Levcopoulos

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

Abstract

This paper considers the problem of finding a quickest path between two points in the Euclidean plane in the presence of a transportation network. A transportation network consists of a planar network where each road (edge) has an individual speed. A traveler may enter and exit the network at any point on the roads. Along any road the traveler moves with a fixed speed depending on the road, and outside the network the traveler moves at unit speed in any direction. We give an exact algorithm for the basic version of the quickest path problem: given a transportation network with n edges in the Euclidean plane, a source point s ∈ R2 and a destination point t ∈ R2, find the quickest path between s and t. We also show how the transportation network can be preprocessed in time O(n2 log n) into a data structure of size O(n22) such that (1 + ε)-approximate quickest path cost queries between any two points in the plane can be answered in time O(1=ε4 log n).

Original languageEnglish
Title of host publicationTheory of Computing 2012 - Proceedings of the Eighteenth Computing
Subtitle of host publicationThe Australasian Theory Symposium, CATS 2012
Pages37-46
Number of pages10
Volume128
Publication statusPublished - 24 Jul 2012
EventTheory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012 - Melbourne, VIC, Australia
Duration: 31 Jan 20123 Feb 2012

Other

OtherTheory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012
CountryAustralia
CityMelbourne, VIC
Period31/01/123/02/12

Fingerprint

Data structures
Costs

Cite this

Shawi, R. E., Gudmundsson, J., & Levcopoulos, C. (2012). Quickest path queries on transportation network. In Theory of Computing 2012 - Proceedings of the Eighteenth Computing: The Australasian Theory Symposium, CATS 2012 (Vol. 128, pp. 37-46)
Shawi, Radwa El ; Gudmundsson, Joachim ; Levcopoulos, Christos. / Quickest path queries on transportation network. Theory of Computing 2012 - Proceedings of the Eighteenth Computing: The Australasian Theory Symposium, CATS 2012. Vol. 128 2012. pp. 37-46
@inproceedings{b33c3d4971a14ed7a93bd9ce0543969d,
title = "Quickest path queries on transportation network",
abstract = "This paper considers the problem of finding a quickest path between two points in the Euclidean plane in the presence of a transportation network. A transportation network consists of a planar network where each road (edge) has an individual speed. A traveler may enter and exit the network at any point on the roads. Along any road the traveler moves with a fixed speed depending on the road, and outside the network the traveler moves at unit speed in any direction. We give an exact algorithm for the basic version of the quickest path problem: given a transportation network with n edges in the Euclidean plane, a source point s ∈ R2 and a destination point t ∈ R2, find the quickest path between s and t. We also show how the transportation network can be preprocessed in time O(n2 log n) into a data structure of size O(n2=ε2) such that (1 + ε)-approximate quickest path cost queries between any two points in the plane can be answered in time O(1=ε4 log n).",
author = "Shawi, {Radwa El} and Joachim Gudmundsson and Christos Levcopoulos",
year = "2012",
month = "7",
day = "24",
language = "English",
isbn = "9781921770098",
volume = "128",
pages = "37--46",
booktitle = "Theory of Computing 2012 - Proceedings of the Eighteenth Computing",

}

Shawi, RE, Gudmundsson, J & Levcopoulos, C 2012, Quickest path queries on transportation network. in Theory of Computing 2012 - Proceedings of the Eighteenth Computing: The Australasian Theory Symposium, CATS 2012. vol. 128, pp. 37-46, Theory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012, Melbourne, VIC, Australia, 31/01/12.

Quickest path queries on transportation network. / Shawi, Radwa El; Gudmundsson, Joachim; Levcopoulos, Christos.

Theory of Computing 2012 - Proceedings of the Eighteenth Computing: The Australasian Theory Symposium, CATS 2012. Vol. 128 2012. p. 37-46.

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

TY - GEN

T1 - Quickest path queries on transportation network

AU - Shawi, Radwa El

AU - Gudmundsson, Joachim

AU - Levcopoulos, Christos

PY - 2012/7/24

Y1 - 2012/7/24

N2 - This paper considers the problem of finding a quickest path between two points in the Euclidean plane in the presence of a transportation network. A transportation network consists of a planar network where each road (edge) has an individual speed. A traveler may enter and exit the network at any point on the roads. Along any road the traveler moves with a fixed speed depending on the road, and outside the network the traveler moves at unit speed in any direction. We give an exact algorithm for the basic version of the quickest path problem: given a transportation network with n edges in the Euclidean plane, a source point s ∈ R2 and a destination point t ∈ R2, find the quickest path between s and t. We also show how the transportation network can be preprocessed in time O(n2 log n) into a data structure of size O(n2=ε2) such that (1 + ε)-approximate quickest path cost queries between any two points in the plane can be answered in time O(1=ε4 log n).

AB - This paper considers the problem of finding a quickest path between two points in the Euclidean plane in the presence of a transportation network. A transportation network consists of a planar network where each road (edge) has an individual speed. A traveler may enter and exit the network at any point on the roads. Along any road the traveler moves with a fixed speed depending on the road, and outside the network the traveler moves at unit speed in any direction. We give an exact algorithm for the basic version of the quickest path problem: given a transportation network with n edges in the Euclidean plane, a source point s ∈ R2 and a destination point t ∈ R2, find the quickest path between s and t. We also show how the transportation network can be preprocessed in time O(n2 log n) into a data structure of size O(n2=ε2) such that (1 + ε)-approximate quickest path cost queries between any two points in the plane can be answered in time O(1=ε4 log n).

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

M3 - Conference contribution

SN - 9781921770098

VL - 128

SP - 37

EP - 46

BT - Theory of Computing 2012 - Proceedings of the Eighteenth Computing

ER -

Shawi RE, Gudmundsson J, Levcopoulos C. Quickest path queries on transportation network. In Theory of Computing 2012 - Proceedings of the Eighteenth Computing: The Australasian Theory Symposium, CATS 2012. Vol. 128. 2012. p. 37-46