Voronoi Diagram

The partitioning of a plane with $n$ points into $n$ 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.