Voronoi tessellation

For any (topologically) discrete set S of points in Euclidean space and for almost any point x, there is one point of S to which x is closer than x is to any other point of S. The word "almost" is occasioned by the fact that a point x may be equally close to two or more poins of S. If S contains only two points, a, and b, then the boundary between the set of all points closer to a than to b and the set of all points closer to b than to a (equidistant) is a hyperplane --- an affine subspace of codimension 1. In general, the set of all points closer to a point c of S than to any other point of S is the interior of a (in some cases unbounded) convex polytope. To each point of S one such polytope is assigned. The set of such polytopes tesselates the whole space, and is the Voronoi tessellation corresponding to the set S. Each of the polytopes separately is a Dirichlet domain. If the dimension of the space is only 2, then it is easy to draw pictures of Voronoi tessellations, and in that case they are sometimes called Voronoi diagrams.

Generalizations are possible to metrics other than Euclidean. However in these cases the Voronoi tessellation is not guaranteed to exist (or to be "true" tessellation), since the equidistant for two points may fail to be subspace of codimension 1, even in the 2-dimensional case. Hence "Voronoi diagram" is a less restrictive term to describe the partition of the space by Voronoi polytopes.