Our first example of a Voronoi diagram consists of only two seeds (the black dots) and two cells, where the line connecting the two seeds is also shown. The maroon region contains the points in the plane closest to the left-hand seed, and the blue region the right. The divider between the two regions bisects the line between the two seeds (since the midpoint is by definition equidistant from the two endpoints) and is in particular the perpendicular bisector of this line. We now present a more complicated example.
In this image, the dots again represent the seeds, while the differently colored regions are the cells of the diagram. The inner region is bounded by a polygon (specifically a pentagon) whose sides are perpendicular bisectors of the lines connecting each of the outer seeds to the center seed. Note also that the central region is finite, since the center seed is surrounded by other seeds, while the other regions extend outward forever. Finally, each point at which three regions meet is the circumcenter of the triangle formed by three nearby seeds. The image below illustrates this fact for our example with six seeds.
Three of the seeds have been connected to form a triangle (white). The circumcenter of the triangle is the center of the circle containing the triangle's three vertices (black). By the definition of a circle, the circumcenter (red) is equidistant from the three seeds and is therefore the point at which the three neighboring regions meet.
Further, regular patterns of seeds produce correspondingly regular patterns of the cells. For example, a repeating square lattice of points produces a repeating pattern of square cells, as shown below.
The reader may experiment with different seed placements using the interactive feature found here. There are many ways to generalize the Voronoi Diagram concept beyond the two-dimensional plane. For example, it is possible to construct three-dimensional Voronoi diagrams, again using points as seeds, except that space will now be divided into three-dimensional cells instead of two.
The above image shows a number of seeds scattered in three-dimensional space and a single cell corresponding to the seed at the center. The lines connecting the center seed to the surrounding ones are also shown. Instead of a polygon, the cell is a polyhedron, bounded by faces which are sections of the planes that form the perpendicular bisectors of the line segments connecting the seeds.
In mathematics, Voronoi diagrams are useful for visualizing the notion of a metric. Metrics are generalizations of the familiar concept of distance to a number of different spaces in addition to the normal Euclidean plane and space (which we have worked with so far). For example, consider the surface of a sphere, such as the Earth. Typically, we define the distance between two points to be the length of the straight line connecting them (which in Euclidean space is the shortest path between the points). However, given two points on the Earth (a sphere), the line connecting them might go through the interior. When we speak of "distance" on the sphere, we want the shortest path along the surface between the two given points, or in other words the fastest travel route from one to the other!
The shortest distance between the points A and B above on the sphere is not the latitude line that they share (though this would be the straight path between them on the 2D map projection) but the arc of a circle passing through the sphere's center. These circles are known as great circles. The distance between two points on a sphere is defined to be the length of the great circle arc connecting them. This is also why planes take what appear to be inefficient paths on two-dimensional maps: they are in fact following a great circle (see below).
Having defined a metric for the sphere, we may choose some collection of points on it and create Voronoi diagrams, just as before. The diagram below takes major airports around the world as seeds and constructs a Voronoi diagram on the Earth's surface (which, of course, is nearly a sphere).
Voronoi diagrams also have a number of applications outside mathematics in settings where understanding distances from a fixed set of sources is important. They are used in modeling the spread of disease, the growth of forests, cell development, the distribution of minerals in the Earth's crust, and rainfall maps, among other things. They are a beautiful visual tool for comprehending the relative positions of points in a given space.
Sources: http://alexbeutel.com/webgl/voronoi.html, http://www.iue.tuwien.ac.at/phd/klima/node21.html, http://www.pitt.edu/~jdnorton/teaching/HPS_0410/chapters/non_Euclid_curved/Geodesic3.gif, http://beautifulnow.is/bnow/the-quest-for-beautiful-data
Nice post thankks for sharing
ReplyDelete