info prev up next book cdrom email home

Voronoi Diagram

\begin{figure}\begin{center}\BoxedEPSF{VoronoiDiagram.epsf}\end{center}\end{figure}

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.




© 1996-9 Eric W. Weisstein
1999-05-26