CVT Milestone

When we talked earlier about the Voronoi diagram of a set of "generator points" G, our focus seemed to be on the points G, and understanding how they implicitly clustered nearby points. We may have noticed that the Voronoi polygons induced by the generator points could be of a wide variety of sizes and shapes.

Now, rather than focussing on the points G, we are going to focus on a region R. We imagine that the points G are a tentative sampling of R, but that we are looking for the best set of points G, which induces the "nicest" subdivision of R into regions of similar size and shape. It turns out that a mathematically reasonable definition of this situation requires that the points G each be the centroid of the subregion they induce, which is an easy condition to check, but not so easy to enforce. However, if we are willing to carry out an interative process, we can gradually modify our point set G to approximate this special arrangement, which is known as a centroidal Voronoi Tessellation, or, because no one wants to say that twice, a "CVT".

For simplicity, let's assume that we have constructed a Voronoi diagram for a set of generator points G that are inside a region R which is a square. This will define, for each point G(i), a polygonal region P(i) of points that are closer to G(i) than to any other generator.

We can imagine that every point in the region wants to be as close as possible to a generator. A reasonable measure of closeness is the square of the distance. In order to consider all the points in polygon P(i), we have to compute the integral of this squared distance, which we label E(i), called the "energy" of polygon P(i). If we sum up the energies over all the polygons, we have the total energy E for this arrangement.

Clearly, except in a few very peculiar cases, E will not be zero. Moreover, the value of E clearly depends on the locations of the generators G. And it's interesting to wonder whether we can reduce E by using a different set of generators. But in fact, this is easy to do. For each polygon P(i), if we simply replace G(i) by the centroid of P(i), you can show that the value of E(i) goes down, and so the total energy E goes down. Hence, this arrangement reduces the clustering energy.

But we can reduce the energy even more; because we moved the points, we should recompute the Voronoi diagram, and this effectively guarantees that some points reduce their energy simply because the new generator locations are closer to them.

It turns out that by repeatedly using points G to compute Voronoi polygons, and the using the centroids of the Voronoi polygons to replace G, the sequence of points G approaches what is called a centroidal Voronoi Tessellation (CVT). Such a set of points G has the property that when you use the points G to compute the Voronoi diagram, the centroids of the polygons are identical to G.

Topics:

• In the 2D case, we generally can't do exact calculations of the Voronoi diagram and the centroids of its subregions, especially if the boundary of the region is curved or very complex. In the special case where the points G are contained in a square, then it is possible to work out an approach that will be exact, but the calculations are tricky, particularly because of the difficulty of dealing with the boundary; therefore, we prefer to use a sampling approach. So our first example will be the computation of a CVT inside the unit square.
• We can compute a CVT for a polygonal region. The important step is setting up the sampling method. If we can represent the polygon as a collection of triangles, then we know what to do.
• We can compute the CVT for a circle. The only tricky thing here is to modify the sampling method, as we discussed in the sampling notebook.
• Problems in higher dimensions can be set up the same way. We have to set up a sampling procedure, and you should know that getting accurate results by sampling becomes harder and harder as the dimension increases. Also, we will have trouble making plots. But as a simple example, we can seek a CVT of the unit cube using 10 generators, and see if the estimated result gives each generator about 1/10 of the total volume.
• Using random sampling, we can also easily incorporate density functions, which are important when we are modeling situations where the properties of space vary, or where there is a varying population density; but we will wait til the "density notebook" to look at this.