- Centroidal Voronoi Diagrams
- Generating Centroidal Voronoi Diagrams

- Resolution of Voronoi Calculation

Voronoi Diagrams

where and are any two points in the plane. The set of points in the plane identified with a particular generator form that generator's Voronoi region, and the set of Voronoi regions covers the entire plane. Figure 1 illustrates a set of generating points and their associated Voronoi regions.

We implemented the the fast 3D graphics hardware-based algorithm in Hoff [5] and originally in [11] to compute our Voronoi diagrams. The algorithm draws a set of right cones with their apexes at each generator. The cones all have the same height and are viewed from above the apexes with an orthogonal projection. In addition, each cone is given a unique colour which acts as the generator's identity. Since the cones must intersect if there is more than one generator, the z-buffer determines for each pixel which cone is closer to the viewer and assigns that pixel the appropriate colour value. We can then scan the resulting image and determine which generator is closest to each pixel by using the unique colours. This technique allows us to compute discrete Voronoi diagrams extremely quickly and perform computations on the resulting regions.

Centroidal Voronoi Diagrams

where is the region, is the position and is the density function. For a region of constant density , the centroid can be considered as the centre of mass. Figure 1 has the centroids of each region marked with small circles.

A centroidal Voronoi diagram is a minimum-energy configuration in the sense that it minimises [2]. Practically speaking, a centroidal distribution of points is useful because the points are well-spaced in a definite sense. Figure 2 shows a centroidal Voronoi diagram.

Generating Centroidal Voronoi Diagrams

Figure 1 relaxes under Lloyd's algorithm to become Figure 2. The convergence of Lloyd's algorithm to a centroidal Voronoi diagram has been proven for the one-dimensional case and higher dimensions seem to act similarly [2]. There are several different convergence criteria which should be equivalent in the limiting case as the algorithm runs forever. The obvious criteria to use would be that the computed centroids are numerically equal to the generating points. However, for most applications this criteria is far too stringent and it would be perhaps better to look at the average distance moved by all generating points. Since we are interested in generating well-spaced sets of points, we look at the average change in inter-point distance, or equivalently, the average change in Voronoi region area.

Efficient Computation of Centroids

The denominator of the centroid is transformed as follows:

where can be precomputed from the density function

The numerator of the y-coordinate of the centroid is transformed similarly:

The numerator of the x-coordinate of the centroid involves integration by parts:

where can also be precomputed from the density function.

Note that the final expressions require numerical integration only in the y-direction and otherwise involve expressions only at the region boundaries and . and are precomputed once from the density function and then evaluated at the horizontal endpoints and as needed. This allows us to compute the integrands only at region boundaries and not at every pixel. Otherwise we would have to compute the integrands and for every span of pixels across a region and numerically integrated. The above integrand computation is particularly simple - at worst two lookups for and , a multiplication and a subtraction.

Resolution of Voronoi Calculation

- ...
function
^{2} - Recall that