Karlsruhe-Metric Voronoi Diagram


    In Manhattan, we can move along either North-South streets or East-West avenues. In Karlshue, we can move along either radiating streets from the center or circular avenues around the center. Specifically, let (r, θ) and (ri, θi) be the polar coordinates of p and pi, respectively, where 0 < θ, θi< 2π, r, ri > 0, and δ(θ,θi) = min { |θ - θi|, 2π - |θ - θi|}

Then, the Karlsruhe metric or Moscow metric from p to pi is defined by

                    min {r, ri} δ(θ,θi) + | r - ri |     for 0 ≤ δ(θ,θi) < 2
dk(p1 pi ) =   r + ri                                                  for 2 ≤ δ(θ,θi) < π

  If we apply the above metric to the bisector, the set vk = {V(p1), . . . , V(pn)} gives generalized Voronoi diagram. This type of Voronoi diagram is known as the Karlsruhe Voronoi Diagram or simply the Karlsruhe Voronoi Diagram.



[1] T. Koshizuka and O. Kurita, "A theoretical study on the role of a circular part of radial-circular networks", Papers of the Annual Conference of the City Planning Institute of Japan, 21(1986), p. 217-222.

[2] R. Klein, "Abstract Voronoi diagrams and their applications Lecture Notes in Computer Science", 333 (International Workshop on Computational Geometry, Wurzburg, March 1988), Springer-Verlag, pp. 148-157.