Quickest Paths, Straight Skeletons, and the City Voronoi Diagram

• DOI: 10.1007/s00454-003-2947-0
• Publication Date: 2003-12-23T19:42:33Z
• Authors: Oswin Aichholzer; Franz Aurenhammer; Bel�n Palop
• Keywords: Centroidal Voronoi tessellation; Power diagram; Weighted Voronoi diagram

The city Voronoi diagram is induced by quickest paths in the L 1plane, made faster 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 relationship 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.