Voronoi Diagram

Voronoi diagrams are wonderful geometric shapes , the more I learn about them, the more fascinated I become. These shapes are inherent in nature, we can see examples of Voronoi regions around us. But first let me explain in my own words about Voronoi diagrams.

Let us take some point sites in a plane. Now our task is to divide the total space into convex polygons or regions surrounding the sites in such a way that , all the points inside the polygon surrounding a site will be closer to that site than any other site of the plane. The diagram we get this way is our desired Voronoi diagram.

Seems a simple one to think. If we restrict the problem in a way that instead of polygon we have to draw circles, then we just take point circles centering the sites and increase their radii until they intersect any other circle. This way each circle contains points that are closer to their centre than any other circle in the plain. But there will be many point that will not be included in any of the circles, so now we have to think about polygon so that all the points will belong to a polygon, no points left aside.

Suppose, we have a set of stars and planets. Now we have to find out which planet belong to which star. If we draw the Voronoi diagram considering the stars as the pint sites then we get the space partitioned with polygons.

If a planet falls inside a polygon P that contains star S, then certainly the planet revolves around S as it is closer to this star than any other star of the constellation. The gravitic field of S is stronger onto the planet than any other star.

Voronoi diagrams have widespread applications in areas such as computer graphics, epidemiology, geophysics, and meteorology. A particularly notable use of a Voronoi diagram was the analysis of the 1854 cholera epidemic in London, in which physician John Snow determined a strong correlation of deaths with proximity to a particular (and infected) water pump on Broad Street.-mathworld

Voronoi diagram in Dragon fly wing