Quickest paths, straight skeletons, and the city Voronoi diagram (Q1424315)

The authors propose and study the following model of transportation network: a set of horizontal and vertical segments in the plane represent ``fast'' links. The speed of moving on fast links is \(v>1\) and otherwise the time needed for moving is given by \(L_1\)-metric in the plane. The problem addressed by the authors is the following: given a set of \(n\) sites in the plane, partition the points of the plane into \(n\) regions according to that which of the \(n\) sites can be reached fastest. This leads to so-called \textit{city Voronoi diagram}. For \(c\) links and \(n\) sites, the authors show an algorithm running in time \(O(n\log n+c^2\log c)\) for construction of refined city Voronoi diagrams (a more compact version of of city Voronoi diagrams) and show that complexity of such diagrams does not exceed \(O(n+c)\).