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:


Last revised on 30 October 2016.