Voronoi diagram

A Voronoi diagram, also known as a Dirichlet tesselation, is a partitioning of space into cells, each of which consists of the points closer to one particular object than to any others. More specifically, in two dimensions a Voronoi diagram consists of breaking up a plane containing n points into n convex polygons in such a way that each polygon contains exactly one point and every point in a given polygon is closer to its central point than to any other. Voronoi diagrams, their boundaries (known as medial axes) and their duals (called Delaunay triangulations) have been reinvented, given different names, generalized, studied, and applied many times over in many different fields. Voronoi diagrams tend to be involved in situations where a space should be partitioned into "spheres of influence", examples of which include models of crystal and cell growth and protein molecule volume analysis.