Advanced

Quickest path queries on transportation network

El Shawi, Radwa; Gudmundsson, Joachim and Levcopoulos, Christos LU (2014) In Computational Geometry 47(7). p.695-709
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 R-2, 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:
author
organization
publishing date
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
0925-7721
DOI
10.1016/j.comgeo.2014.01.004
language
English
LU publication?
yes
id
c8cb6000-ef83-40d1-9bec-09d36662a24d (old id 4558653)
date added to LUP
2014-07-17 12:58:11
date last changed
2017-01-01 06:24:02
@article{c8cb6000-ef83-40d1-9bec-09d36662a24d,
  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 R-2, 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         = {0925-7721},
  keyword      = {Computational geometry,Approximation algorithms,Shortest path,Transport networks},
  language     = {eng},
  number       = {7},
  pages        = {695--709},
  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},
}