Voronoi tesselation

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 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 tesselation corresponding to the set S. If the dimension of the space is only 2, then it is easy to draw pictures of Voronoi tesselations, and in that case they are sometimes called Voronoi diagrams.