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ε)2logn) into a data structure of size O((nε)2) such that (1+ε)(1+ε)-approximate quickest path cost queries between any two points in the plane can be answered in time O(1ε4logn).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 ZZ of m   sites, a query point q∈R2q∈R2, find the nearest site in ZZ from q  . We show how the transportation network can be preprocessed in time O((n2+nm)log(n+m))O((n2+nm)log(n+m)) such that (1+ε)(1+ε)-nearest neighbor query can be answered in time O(1ε2log(n+m)).