Quickest Paths, Straight Skeletons, and the City Voronoi Diagram

O. Aichholzer, F. Aurenhammer, and B. Palop


The city Voronoi diagram is induced by quickest paths, in the $L_1$ 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.

Reference: O. Aichholzer, F. Aurenhammer, and B. Palop. Quickest paths, straight skeletons, and the city Voronoi diagram. Discrete & Computational Geometry, 31(1):17-35, 2004.