Technical Report No. 7, December 1987 - Abstract

Rolf Klein:
Voronoi diagrams in the Moscow Metric

This report is not available in electronic form!

Most of the streets of Moscow are either radii emanating from the Kremlin, or pieces of circles around it. We show that Voronoi diagrams for n points based on this metric can be computed in optimal O(n*log n) time and linear space. To this end, we prove a general theorem stating that bisectors of suitably separated point sets do not contain loops if, beside other properties, there are no holes in the circles of the underlying metric. Then the Voronoi diagrams can be computed within O(n*log n) steps, using a divide-and-conquer algorithm. This theorem not only applies to the Moscow metric but to a large class of metrics including the symmetric convex distance functions and all composite metrics obtained by assigning the L1 or the L2 metric to the regions of an arbitrary planar map.