Title: “The big sweep”: On the power of the wavefront approach to Voronoi diagrams
Abstract: 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.
Publication Year: 1994
Publication Date: 1994-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 2
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot