## DyingLoveGrape.## A Brief Introduction to Veronoi and Delaunay Diagrams.## Point on a Plane and Closest Regions.Let's plot a set of points. They can be essentially random for now, but note that this could stand for some kind of real-world data. Here it is:
Now let's tell a story. Once upon a time there were five greedy sisters who were given houses built on a countryside. They decided, being greedy, that they wanted to fence in their property. Since they didn't want too much conflict, they agreed that they'd only fence off land that was
Such a plot is called a Looking at a more realistic case, suppose there are 10 power stations scattered around some town, and they want to know (at least approximately) which homes they should power. Suppose, for the problem, that they don't need to worry about how much power, they just want to worry about minimizing loss: they'd like to power the closest houses that they can. This seems like a problem tailor-made for Voronoi diagrams. Let's picture this: It's a bit difficult to distinguish between some of the blue colors here, but there are exactly ten Voronoi polygons, one containing each point. What this says is, the power plants should zone the city according to this mapping and, for example, if a house falls in one of the power station's Voronoi polygons then it should be powered by that station. There are too many examples of Voronoi diagrams being useful for me to list. I've seen it be applied to the recreation of virtual tumors from points given by an $x$-ray, looking at nerve pathways, and where to run public transport so that people can more easily trek about a city.
## Graphs and their Duals.We'll take a brief interlude from Voronoi diagrams to talk a bit about graphs. We'll need this at the end of the post, but since Delaunay triangulations form a graph it's a good time to introduce them. A graph is a collection of vertices and edges which are assembled in a nice way:
This doesn't look much like our Voronoi diagrams above, which is a bit upsetting, but that's okay; we didn't really expect them to in the first place. Either way, one neat thing we can do to graphs is to take their - First, put one vertex inside of each closed polygons your graph makes. Also, put one vertex somewhere on the outside of all the closed-in polygons of your graph.
- Second, draw edges between each vertex if their closed polygonal regions were next to each other in the original graph; also, if the region was next to the "outside" of the graph, connect that vertex in the dual to the "outside" vertex.
Congratulations! You've made a dual graph. The idea is sort of like this: points in the dual correspond to closed-in polygons in the original graph. Each edge in the original graph should be crossed once and only once by an edge in the dual. It's much easier to show a picture of this than to describe it. The blue graph is the original graph, the red graph is the dual. We will talk about duals in a future post; at times, it is easier to work with a dual than it is to work with the original structure and (generally) if one proves a theorem for an original structure the theorem will also be able to be "dualized". ## Delaunay Triangulations.The Delaunay Triangulation is a strange structure. The idea is like this: - Take some number of points (let's say, for now, on the plane).
- Now connect the points such that the entire figure is now "made up of" triangles (i.e., triangulate). Look at the picture below for an idea of what this means.
- Pick a triangle and look at its three vertices: draw a circle which contains all these vertices. If none of your original points are inside the cirlce, good: keep going until you've exhausted all of the triangles. If any of the original points are inside of any of the circles then this is not a valid triangulation: go back to the previous step and try again.
The figure above shows all of the circles that we made in this triangulation; note that none of these circles contains, on the inside, any of the other points that we started with. If this is the case, then we call the graph that we've made (the original points and the edges forming the triangles) a As you might expect after reading the last section, the Delaunay triangulation is
Pretty neat, no? Notice that it is not Each partition of the plane these points make is a Voronoi polygon. In the figure above, make sure that you count exactly five Voronoi polygons and, moreover, note that each of our original points is in exactly one of these! Almost like magic. It's instructive to make an "incorrect" Delaunay triangulation (allowing one of the circles to contain an original point on its interior) and see what goes wrong. Usually, it's the case that more than one original point is in the Voronoi polygon. Note also that it is not always possible to make a Delaunay triangulation: for example, if you have three colinear points it's impossible to create a circle which passes through all of them. There are other criteria which make these triangulations impossible; see if you can find a few!
Last, even if the triangulation exists, it is not usually unique. Drawing a square and attempting to triangulate gives us two different triangulations: the diagonal up-left to bottom-right, and the diagonal bottom-left to up-right. This non-uniqueness might seem strange to you: the Veronoi diagram Think about the square again; look at the centers of the circles that one makes for each different triangulation: the centers will be the same and, hence, will not create any differences when one is constructing the duals. Do any other kinds of ambiguities come up in when making Delaunay triangulations? ## Next time...Next time, we'll look at some applications of Delaunay Triangulations and Voronoi Diagrams. |