info prev up next book cdrom email home

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


Eppstein, D. ``Nearest Neighbors and Voronoi Diagrams.''

© 1996-9 Eric W. Weisstein