On Voronoi Diagrams for Lines in the Plane

We describe a method based on the wavefront propagation, which computes a multiplicatively weighted Voronoi diagram for a set L of n lines in the plane in O(n 2 log n) time and O(n 2 ) space. In the process, we derive complexity bounds and certain structural properties of such diagrams. An advantage...

Full description

Saved in:
Bibliographic Details
Main Authors: Barequet, G., Vyatkina, K.
Format: Conference Proceeding
Language:English
Subjects:
Application software
Computer graphics
Computer science
Euclidean distance
generalized Voronoi diagrams
Machinery
Mathematics
wavefront propagation
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We describe a method based on the wavefront propagation, which computes a multiplicatively weighted Voronoi diagram for a set L of n lines in the plane in O(n 2 log n) time and O(n 2 ) space. In the process, we derive complexity bounds and certain structural properties of such diagrams. An advantage of our approach over the general purpose machinery, which requires computation of the lower envelope of a set of halfplanes in three-dimensional space, lies in its relative simplicity. Besides, we point out that the unweighted Voronoi diagram for n lines in the plane has a simple structure, and can be obtained in optimal thetas(n 2 ) time and space.
DOI:10.1109/ICCSA.2009.39