plane
speeded up by an isothetic transportation network. We investigate the 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 the distance model and the wavefront model. Especially, straight skeletons are a relevant example where an interpretation in the former model is lacking. We clarify the relation between these models, and further draw a connection to the bisector-defined abstract Voronoi diagram model, with the particular goal of computing the city Voronoi diagram efficiently.