Voronoi Diagram and Delaunay Triangulation
- The Voronoi Diagram of a finite set of points (sites) in the plane
consists of a finite set of edges and points (Voronoi vertices) that
subdivide the plane into regions (Voronoi cells), such that each
region contains only one site, and any point inside a region is closer
to the site it contains than to any other site
- Here we are only interested in computing the Voronoi Diagram for the image
points, that is, for points in the complex plane
- The dual of the Voronoi Diagram, the Delaunay Triangulation, can
be easily obtained from the Voronoi Diagram, by connecting by an edge
all sites that are neighbors, that is, all sites that have a Voronoi
edge in common
