Institute of Theoretical Informatics, Algorithmics

Voronoi Diagram for the City-Metric

Voronoi regions that take roads into account

Given a set S of n point sites in the plane, the City Voronoi diagram partitions the plane into the Voronoi regions of the sites, with respect to the City metric. This metric is induced by quickest paths according to the Manhattan metric and an accelerating transportation network that consists of c non-intersecting axis-parallel line segments. We describe an algorithm that constructs the City Voronoi diagram (including quickest path information) in O( (c + n) polylog(c + n) ) time using a wavefront expansion. The below figure depicts a City Voronoi diagram and a partial wavefront expansion.

Awards

On October 10, 2005, Robert Görke won the award “Best presentation of a young speaker” at the Second International Symposium on Voronoi Diagrams in Science and Engineering (VD'05) for presenting the paper [1].

At the same conference he won the Cover Artwork Competition for the proceedings with the above figure.

Publications

  1. Robert Görke, Chan-Su Shin, and Alexander Wolff. Constructing the city Voronoi diagram faster. International Journal of Computational Geometry and Applications, 18(4), 2008. To appear. [ bib | pdf | abstract ]
  2. Robert Görke and Alexander Wolff. Constructing the city Voronoi diagram faster. In Proc. 2nd Internat. Symp. on Voronoi Diagrams in Science and Engineering (VD'05), pages 162-172, Seoul, 2005. [ bib | pdf ]
  3. Robert Görke and Alexander Wolff. Constructing the city Voronoi diagram faster. In Proc. 21st European Workshop on Computational Geometry (EWCG'05), pages 155-158, Eindhoven, 2005. [ bib | pdf ]
  4. Robert Görke. Ein schneller Konstruktionsalgorithmus für eine Quickest-Path-Map bezüglich der City-Metrik. Master's thesis, Fakultät für Informatik, Universität Karlsruhe, September 2004. [ bib | pdf ]