Quickest path queries on transportation network

Summary, in English

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: Radwa El Shawi; Joachim Gudmundsson; Christos Levcopoulos
• Department/s: Department of Computer Science; Parallel Systems
• Publishing year: 2014
• Language: English
• Pages: 695-709
• Publication/Series: Computational Geometry
• Volume: 47
• Issue: 7
• Links: http://dx.doi.org/10.1016/j.comgeo.2014.01.004
• Document type: Journal article
• Publisher: Elsevier
• Topic: Computer Science
• Keywords: Computational geometry; Approximation algorithms; Shortest path; Transport networks
• Status: Published
• ISBN/ISSN/Other: ISSN: 0925-7721