In this paper we present a new generalization of the Voronoi diagram in the plane, in which we shift our interest from points to lines, that is, we compute the partition of the set of lines in the plane into sets of lines having the same closest site (where sites are points in the plane). We first define formally this diagramand give first properties. Then we use a duality relationship between points and lines to visualize this data structure and give more properties. We show that the size of this line space Voronoi diagram for n sites is in \Theta(n^2) and give an optimal algorithm for its explicit computation.

We then show a remarkable relationship between this diagram and the dual arrangement of the sites and give a new result on an arrangement of lines: we show that the size of the zone of a line augmented with its incident faces is still in O(n). We finally apply this result to show that the size of the zone of a line in the line space Voronoi diagram is in O(n).