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² log n) time and O(n²) 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²) time and space.