An Overview of Voronoi Diagrams and Triangulation
What is a Voronoi Diagram?
Voronoi diagrams can be applied to and used in most science and engineering fields, anything from art and UI to robotics and astrophysics (Lynch, Wikipedia) - almost any circumstance where you have a discrete set of data and care about distance. Visually they are maps of surfaces divided into regions, where all the points within a region are closest to a known site. The voronoi diagram on the right partitions a set of point as shown by the colored cells such that each point is only in one cell.
What is Delaunay Triangulation?
Delaunay triangulations are closely connected to Vornoi diagrams. Given any list of points, its Delaunay triangulation is the set of triangles that connect all the points together to form a web. The catch? The smallest angle in each triangle must be maximized. The diagram on the left shows the Delaunay triangulation in the blue.