Computational Geometry: Voronoi Diagram and Delaunay Triangulation 2011 by Fang, Can 1 Post Office: What is the area of service? q q : free point e e : Voronoi edge v v : Voronoi vertex pi pi : site points Definition of Voronoi Diagram Let P be a set of n distinct points (sites) in the plane. The Voronoi diagram of P is the subdivision of the plane into n cells, one for each site. A point q lies in the cell corresponding to a site pi P iff Euclidean_Distance( q, pi ) < Euclidean_distance( q, pj ), for each pi P, j i. Voronoi Diagram Example:1 site Two sites form a perpendicular bisector Voronoi Diagram is a line that extends infinitely in both directions, and the two half planes on either side. Collinear sites form a series of parallel lines Non-collinear sites form Voronoi half lines that meet at a vertex A Voronoi vertex is the center of an empty circle touching 3 or more sites. v Half lines A vertex has degree 3 Voronoi Cells and Segments v Voronoi Cells and Segments v Unbounded Cell Bounded Cell Segment Existence of Bounded Cells v Which of the following is true for 2-D Voronoi diagrams? Four or more non-collinear sites are… sufficient to create a bounded cell necessary to create a bounded cell 1 and 2 none of above
