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.

• Författare: Radwa El Shawi; Joachim Gudmundsson; Christos Levcopoulos
• Avdelning/ar: Institutionen för datavetenskap; Parallella System
• Publiceringsår: 2014
• Språk: Engelska
• Sidor: 695-709
• Publikation/Tidskrift/Serie: Computational Geometry
• Volym: 47
• Issue: 7
• Länkar: http://dx.doi.org/10.1016/j.comgeo.2014.01.004
• Dokumenttyp: Artikel i tidskrift
• Förlag: Elsevier
• Ämne: Computer Science
• Nyckelord: Computational geometry; Approximation algorithms; Shortest path; Transport networks
• Status: Published
• ISBN/ISSN/Övrigt: ISSN: 0925-7721