Generalization of Voronoi Diagrams in the Plane

Abstract

In this paper we study the Voronoi diagram for a set of N line segments and circles in the Euclidean plane. The diagram is a generalization of the Voronoi diagram for a set of points in the plane and has applications in wire layout, facility location, clustering and contouring problems. We present an $O(N(\log N)^2 )$ algorithm for constructing the diagram. It is an improvement of a previous known result which takes $O(Nc^{\sqrt {\log N} } )$ time. The algorithm described in this paper is also shown to be applicable under a more general metric if certain conditions are satisfied.