Quickest Paths, Straight Skeletons, and the City Voronoi Diagram

The city Voronoi diagram is induced by quickestpaths in the L ₁plane, made faster by an isothetic transportation network. We investigatethe rich geometric and algorithmic properties of city Voronoi diagrams,and report on their use in processing quickest-path queries. In doing so, we revisit the fact that not every Voronoi-type diagram has interpretations in both thedistance model and the wavefront model.Especially, straight skeletons are a relevant example where aninterpretation in the former model is lacking.We clarify the relationship between these models, and further draw aconnection to the bisector-defined abstract Voronoi diagram model,with the particular goal of computing the city Voronoi diagram efficiently.