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
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.
In Proc. Ann. ACM Symp. Computational Geometry, pages
151-159, Barcelona, Spain, 2002.