User:Nackman

From Wikipedia, the free encyclopedia

Voronoi Diagrams: Geometry, Practical Applications, and Their Relation With Delaunay Triangulations

Voronoi Diagrams are used extensively throughout geometry, computer science, and in many practical applications. Although examples of Voronoi diagrams were used in astronomy as early as 1644, Lejeune Dirichlet (1805-1859) was credited with their first discovery in 1850. However, Voronoi diagrams were named after Georgy Voronoi (1868-1908). Voronoi was a Ukrainian mathematician who studied at Warsaw University. He studied Voronoi diagrams extensively, publishing many papers on their applications in other fields of mathematics. The discovery of Voronoi diagrams was prompted by a seemingly simple problem: Given a set of points S on a plane, for each point pi in S, what is the region such that all points of the region are closer to pi than to any other point in S. Voronoi diagrams consist of convex polygonal regions called cells or Voronoi polygons. Each cell is specific to one point in S. In other words, cell Vi contains point pi and no other point in the set. Likewise, all points contained in a Voronoi polygon are closer to the point corresponding with that polygon than to any other point in the set. Every Voronoi polygon shares at least one edge with another polygon. Voronoi polygons have no defined shape and can even be unbounded, continuing infinitely. However, cells in Voronoi diagrams are only unbounded if and only if they are corresponding to points which make up the convex hull of the set. Each vertex on the Voronoi diagram is a junction of exactly three edges (assuming that no four points in the set are co-circular). All edges of a Voronoi diagram are perpendicular bisectors between two points in S. Therefore, given the x and y coordinates of two points corresponding to cells that share an edge, the distance formula, d = √ (x2-x1)2+(y2-y1)2 , can be divided by two to find the distance between either of the points and the edge they share. *2 applications of the distance formula can be seen on the formula applications page.*

The construction of a Voronoi diagram is more complex than it seems. Voronoi diagrams are constructed one Voronoi polygon at a time. First, pick a point pi in S. Construct the perpendicular bisectors between pi and every other point in S. Each time a perpendicular bisector is constructed, it cuts the plane into two halves called half-planes. The Voronoi polygon of pi is the intersection of all of the half-planes containing pi. The resulting polygon is one cell of the Voronoi diagram. This entire process must be repeated for every point in S until all cells are computed. Although effective, this is a lengthy process. If n is the number of points in S, n2-n perpendicular bisectors must be constructed before the Voronoi diagram is complete. For greater n values (more points in S) this is a problem. For example, if n were 1,000, exactly 999,000 perpendicular bisectors must be constructed before the diagram is complete. The “divide and conquer” method more efficiently constructs Voronoi diagrams. Having the most effective method for constructing a Voronoi diagram is very important when using computers (especially with large numbers of points). The first step of the “divide-and-conquer” technique is to divide the set of points roughly in half with a line. Where the points are divided can be determined by grouping the points based on either their x or y coordinates when the set of points is graphed. After set S is divided into S1 and S2, further divide these subsets into S1a, S1b, S2a, and S2b. Continue this dividing process until subsets with only two or three points remain. Using the original method for construction of a Voronoi diagram, construct the diagram for each of these subsets. After all of the subsets’ Voronoi diagrams are constructed, the individual subsets must be reconnected, or in a sense stitched, back together from where they were originally divided. Below is a picture of two separate subsets (formed from reconnected previously smaller subsets) and then a picture of their reconnection. Drawing perpendicular bisecting segments between opposite points forms the bold line or seam, of the two subsets (seen in the picture farthest right).

After constructing a Voronoi diagram, you can use it. In fact, Voronoi diagrams are not only useful, but also important. For example, there are five fire stations in Chapel Hill. In an emergency, the fire department must send out their trucks as quickly as possible. To do this, they must choose to dispatch their trucks from the closest fire station. In this situation, the five fire stations are a set of points. After making a Voronoi diagram of this set of points (or the fire stations), it becomes clear where the trucks should be dispatched from. For highest efficiency, the fire trucks should be dispatched from the station corresponding to the Voronoi polygon that contains the location of the fire. This application of Voronoi diagrams also applies to retail, public transportation, and shipment of resources. Below is a Voronoi diagram displaying locations of retail outlets in San Francisco. Voronoi diagrams are also applied in more complex ways. For example, in astronomy, Voronoi diagrams identify star clusters and galaxies. This is a good example because it is clear how the stars are considered a set of points, which are then divided into a Voronoi diagram. The Voronoi polygons then become galaxies. Voronoi diagrams are also used in biology. By splitting land into Voronoi polygons based on species of plants, plant competition can be studied. Similarly, in archaeology, remnants of pottery and buildings can be setup as a Voronoi diagram, dividing land into different regions of cultural influence. There are at least 30 other practical (real world) applications of Voronoi diagrams including crystallography, geology, metallurgy, cartography, and finite element analysis. Voronoi diagrams also have an interesting relationship with Delaunay triangulations. In fact, Delaunay triangulations are the dual graph of Voronoi diagrams. Duality means that the vertices of a Delaunay triangulation correspond to the cells, in a Voronoi diagram (and vice versa). The word triangulation means connecting a set of points as to form many triangular cells. There are many different types of triangulations for a set of points. However, the Delaunay triangulation has many unique properties. Below is a picture of a Delaunay triangulation superimposed on its dual Voronoi diagram.

When the smallest triangle angles of a Delaunay triangulation are compared to any other triangulation’s smallest angles for the same set of points, the Delaunay triangulation will always have the largest angles. This property makes the Delaunay triangulation suitable for creating a mesh on an element. A mesh is a web of cells used to analyze finite elements. Finite element analysis is used in engineering to solve many kinds of problems including heat flow, stress, and elemental properties. Small angles in meshes make them less effective for analysis, therefore making the Delaunay triangulation highly effective for meshing. Below is a picture of a mesh on a material.

By applying the properties of Delaunay triangulations to Euler’s formula, the formula can be used to find the number of edges, e, and the number of vertices, v. Since in a Delaunay triangulation there are three or more edges to every face, f, (the unbounded region is also considered part of the triangulation and has more than three edges) and each edge belongs to two faces, it can be said that 2e≤3f. By algebra, f ≤⅔e. When Euler’s formula is rewritten to state e=v+f-2, f can be replaced by ⅔e, stating e≤v+⅔e-2. By algebra, e≤3v-6. Since Voronoi diagrams are the duals of Delaunay triangulations, the number of points, n, in a Voronoi diagram is the same as the number vertices, v, in a Delaunay triangulation. Therefore, e≤3n-6 in a Voronoi diagram. Similarly, by applying properties of Delaunay triangulations to Euler’s formula, v≤2n-5 can also be proved. **2 applications of Euler’s formula (modified in this way) can be seen on the formula applications page.** A Delaunay triangulation is the triangulation constructed through the edges of a Voronoi diagram. However, there is a simple formula used to construct a Delaunay triangulation called the Guibas-Stolfi algorithm. This formula basically tests whether or not a fourth point is contained within the circle formed through three other points in a set. Delaunay triangulations happen to be constructed so that when a circle is constructed through the three points in one cell, or triangle, no other point in the set is contained within that circle. Therefore, by knowing whether or not the circle constructed through three points in the set contains another point in the set will allow you to know which three points to connect. The formula uses a determinant and is as follows:

The different sub-coordinates of x and y represent the four different points being computed. If the determinant is in fact less than zero, the fourth point (d) is not contained within the circle through points a, b, and c, and points a, b, and c should be connected to form a Delaunay triangulation. ***2 applications of the Guibas-Stolfi algorithm can be seen on the formula applications page.*** In conclusion, Voronoi diagrams are extremely useful tools in geometry, as well as in other practical fields. Without them, it would be very difficult to map out regions closest to specific locations. Also, as I have made clear, Delaunay triangulations, a Voronoi diagram’s dual, is also very useful. Not only are they useful for meshing for finite element analysis, but they also are used to find properties of Voronoi diagrams. As a pair, Voronoi diagrams and Delaunay triangulations are incredibly important in geometry and math in general.

Formula Application Page:

• The distance formula divided by two to find the distance between a point and an edge of its Voronoi polygon.

1. Point A(0,0) and point B(1,1) correspond to Voronoi polygons which share an edge. Find the distance between point A and the edge shared.

d = √ (0-1)2+(0-1)2 /2 d= √2 /2 Answer: √2 /2

2. Point A(0,0) and point B(10,10) correspond to Voronoi polygons which share an edge. Find the distance between point A and the edge shared.

d = √ (0-10)2+(0-10)2 /2 d= 5√2 Answer: 5√2

• • Euler’s formula modified to state e≤3n-6 and v≤2n-5 for a Voronoi diagram.

1. There are 24 points in set S. Find the greatest possible number of edges in the Voronoi diagram of S.

e≤3*24-6 e≤66 Answer:66

2. Find the greatest possible number of vertices in the Voronoi diagram of S.

v≤2*24-5 v≤43 Answer:43

• • • Using the Guibas-Stolfi algorithm to find out if three points should be connected to form a Delaunay triangulation.

When multiplied out, the formula is as follows: xb(yc[xd2+yd2]- yd[xc2+yc2])- xc(yb[xd2+yd2]- yd[xb2+yb2])+ xd(yb[xc2+yc2]- yc[xd2+yd2])- xa(yc[xd2+yd2]- yd[xc2+yc2])- xc(ya[xd2+yd2]- yd[xa2+ya2])+ xd(ya[xc2+yc2]- yc[xa2+ya2])+ xa(yb[xd2+yd2]- yd[xb2+yb2])- xb(ya[xd2+yd2]- yd[xa2+ya2])+ xd(ya[xb2+yb2]- yb[xa2+ya2])- xa(yb[xc2+yc2]- yc[xb2+yb2])- xb(ya[xc2+yc2]- yc[xa2+ya2])+ xc(ya[xb2+yb2]- yb[xa2+ya2]) <0 (This formula is usually calculated quickly by a computer program. However, it is possible to compute by hand.) 1. Should points A(-2,0), B(2,0), and C(0,2) be connected to form a Delaunay triangulation if point D(0,-3) is in the same set? When plugged in to the above formula, you are left with a number less than zero (a negative number). From this you can conclude that point D is outside the circle formed through points A, B, and C. The points should be connected.

2. Should points A(-2,0), B(2,0), and C(0,2) be connected to form a Delaunay triangulation if point D(0,-1) is in the same set? When plugged in to the above formula, you are left with a number greater than zero (a positive number). From this you can conclude that point D is inside the circle formed through points A, B, and C. The points should not be connected.