An ordinary Voronoi diagram is formed by a set of points in the plane called
the generators or generating points. Every point in the plane
is identified with the generator which is closest to it by some metric. The
common choice is to use the Euclidean distance metric
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.
Voronoi diagram with generators (large dots)
and centroids (small dots)
We implemented the the fast 3D graphics hardware-based algorithm in
Hoff  and originally in  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
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.
A centroidal Voronoi diagram has the odd property that each
generating point lies exactly on the centroid of their Voronoi region.
The centroid of a region is defined as
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
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.
Centroidal Voronoi diagram with generators
Lloyd's method  is an iterative algorithm to
generate a centroidal Voronoi diagram from any set of generating points. The
algorithm can simply be stated:
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 .
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.
Calculating the centroids requires efficiently evaluating the integrals in
equation (1). Since the integrals are over
arbitrary Voronoi regions, we convert to iterated integrals and integrate
the region row by row. In this manner we can precompute much of the integral.
Efficient Computation of Centroids
The denominator of the centroid is transformed as follows:
can be precomputed from the
Note that we cannot precompute the entire integral because we do
not know the boundaries of the Voronoi regions beforehand.
The numerator of the y-coordinate of the centroid is transformed similarly:
The numerator of the x-coordinate of the centroid involves integration
can also be precomputed from the
Note that the final expressions require numerical integration only in the
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.
One disadvantage of using a discrete calculation of the Voronoi regions is the
centroids calculation is effected by the resolution of the diagram. The
relative error of the calculated centroid location will increase as the number
of pixels in the Voronoi region decreases. A related problem is that if
the resolution is low enough, two generating points can effectively overlap
and one of the regions will disappear. The solution, as described in
, is to split the diagram into tiles and compute each
tile at the full resolution available and then stitch the full diagram back
together at a higher virtual resolution. The virtual resolution can be
increased arbitrarily to meet a lower bound on Voronoi region pixel area.
Resolution of Voronoi Calculation
- Recall that