Quickest path queries on transportation network

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