We show that the line sweep approach to Voronoi diagrams can be generalized to a very general class of distance measures called nice metrics. This class is more general than the previously studied convex distance functions. It includes e.g the Moscow metric. We provide the first worst-case optimal algorithm for the full class of nice metrics in the plane. It is conceptually simple and easy to implement, and it copes with all possible deformations of the diagram.

Additional Metadata
Series Lecture Notes in Computer Science
Citation
Dehne, F, & Klein, R. (Rolf). (1994). “The big sweep”: On the power, of the wavefront to Voronoi diagrams. In Lecture Notes in Computer Science.