4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007) Two-dimensional line space Voronoi Diagram University of Glamorgan, Pontypridd, Wales July 09-July 11 ISBN: 0-7695-2869-4
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISVD.2007.39
Given a set of points called sites, the Voronoi diagram is a partition of the plane into sets of points having the same closest site. Several generalizations of the Voronoi diagram have been studied, mainly Voronoi diagrams for different distances (other than the Euclidean one), and Voronoi diagrams for sites that are not necessarily points (line segments for example). 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).
Citation:
St?phane Rivi?re, Dominique Schmitt, "Two-dimensional line space Voronoi Diagram," isvd, pp.168-175, 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007), 2007 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb