The partitioning of a plane with points into convex Polygons such that each Polygon contains exactly one point and every point in a given Polygon is closer to its central point than to any other. A Voronoi diagram is sometimes also known as a Dirichlet Tessellation. The cells are called Dirichlet Regions, Thiessen Polytopes, or Voronoi Polygons.
See also Delaunay Triangulation, Medial Axis, Voronoi Polygon
References
Eppstein, D. ``Nearest Neighbors and Voronoi Diagrams.''
http://www.ics.uci.edu/~eppstein/junkyard/nn.html.