“The big sweep”: On the power, of the wavefront to Voronoi diagrams
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.
|Series||Lecture Notes in Computer Science|
Dehne, F, & Klein, R. (Rolf). (1994). “The big sweep”: On the power, of the wavefront to Voronoi diagrams. In Lecture Notes in Computer Science.