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:
https://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
- 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
- 2016-04-01 14:43:11
- date last changed
- 2022-03-22 01:35:13
@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}},
keywords = {{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}},
doi = {{10.1016/j.comgeo.2014.01.004}},
volume = {{47}},
year = {{2014}},
}