Encyclopedia > Voronoi diagram

  Article Content

Voronoi tesselation

Redirected from Voronoi diagram

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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article

... famous being the Type 35 Grand Prix car, the huge "Royale[?]", and the Type 55 sports car. Bugatti also designed a successful motorized railcar, the Autorail, and an ...

This page was created in 34.2 ms