Quickest path queries on transportation network
(2014) In Computational Geometry 47(7). p.695709 Abstract
 This paper considers the problem of finding the cost of 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 show how the transportation network with n edges in the Euclidean plane can be preprocessed in time O ((n/epsilon)(2) log n) into a data structure of size O ((n/epsilon)(2)) such that (1 + epsilon)approximate quickest path cost queries between any two points in... (More)
 This paper considers the problem of finding the cost of 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 show how the transportation network with n edges in the Euclidean plane can be preprocessed in time O ((n/epsilon)(2) log n) into a data structure of size O ((n/epsilon)(2)) such that (1 + epsilon)approximate quickest path cost queries between any two points in the plane can be answered in time O (1/epsilon(4) log n). In addition we consider the nearest neighbor problem in a transportation network: given a transportation network with n edges in the Euclidean plane together with a set Z of m sites, a query point q is an element of R2, find the nearest site in Z from q. We show how the transportation network can be preprocessed in time O ((n(2) + nm) log (n + m)) such that (1 + epsilon)nearest neighbor query can be answered in time O (1/epsilon(2) log(n + m)). (C) 2014 Published by Elsevier B.V. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/4558653
 author
 El Shawi, Radwa; Gudmundsson, Joachim and Levcopoulos, Christos ^{LU}
 organization
 publishing date
 2014
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 Computational geometry, Approximation algorithms, Shortest path, Transport networks
 in
 Computational Geometry
 volume
 47
 issue
 7
 pages
 695  709
 publisher
 Elsevier
 external identifiers

 wos:000336186100001
 scopus:84897807758
 ISSN
 09257721
 DOI
 10.1016/j.comgeo.2014.01.004
 language
 English
 LU publication?
 yes
 id
 c8cb6000ef8340d19bec09d36662a24d (old id 4558653)
 date added to LUP
 20140717 12:58:11
 date last changed
 20170101 06:24:02
@article{c8cb6000ef8340d19bec09d36662a24d, abstract = {This paper considers the problem of finding the cost of 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 show how the transportation network with n edges in the Euclidean plane can be preprocessed in time O ((n/epsilon)(2) log n) into a data structure of size O ((n/epsilon)(2)) such that (1 + epsilon)approximate quickest path cost queries between any two points in the plane can be answered in time O (1/epsilon(4) log n). In addition we consider the nearest neighbor problem in a transportation network: given a transportation network with n edges in the Euclidean plane together with a set Z of m sites, a query point q is an element of R2, find the nearest site in Z from q. We show how the transportation network can be preprocessed in time O ((n(2) + nm) log (n + m)) such that (1 + epsilon)nearest neighbor query can be answered in time O (1/epsilon(2) log(n + m)). (C) 2014 Published by Elsevier B.V.}, author = {El Shawi, Radwa and Gudmundsson, Joachim and Levcopoulos, Christos}, issn = {09257721}, keyword = {Computational geometry,Approximation algorithms,Shortest path,Transport networks}, language = {eng}, number = {7}, pages = {695709}, publisher = {Elsevier}, series = {Computational Geometry}, title = {Quickest path queries on transportation network}, url = {http://dx.doi.org/10.1016/j.comgeo.2014.01.004}, volume = {47}, year = {2014}, }