Voronoi Diagram - The Simplest Case

The Simplest Case

In the simplest and most familiar case (shown in the first picture), we are given a finite set of points {p₁,...,p_n} in the Euclidean plane. In this case each site p_k is simply a point and its corresponding Voronoi cell (also called Voronoi region or Dirichlet cell) R_k consisting of every point whose distance to p_k is less than or equal to its distance to any other site. Each such cell is obtained from the intersection of half-spaces, and hence it is a convex polygon. The segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest sites. The Voronoi vertices (nodes) are the points equidistant to three (or more) sites.