CVT with Some Generators Fixed

CVT_FIXED is a FORTRAN90 library which can be used to update a centroidal Voronoi tessellation (CVT).

CVT_FIXED attempts to compute a new CVT starting from an existing one, updating some of the cell generators, but leaving designated cell generators fixed. The updated cell generators are replaced by the centroid of their cells.

The user specifies which generators are to be fixed, and which may be updated. Watching an animation of the evolution of the system, the cells corresponding to fixed generators comprise obstacles, and the free cells behave like soap bubbles that flow around the obstacles, trying to balance pressures (cell volume).

A second feature has been added, a maximum influence distance. This is the variable "cutoff_dist". When sampling the region, if the nearest generator is further than this distance, we don't assign the point at all.

The code includes the weight vector that was developed in the CVT_SIZE program. Here, it is anticipated that the weight vector would be used in situations where an initial set of generators has been computed, and is to be augmented. The initial set of generators is held fixed, and the new points are to be allowed to arrange themselves. However, if we place the new points at random, they will get trapped in local minima. By using the weight vector, we can start out with the initial generators having very little influence, and then gradually ramp their weights up to equality with the new points.

We were interested in watching the behavior of the Voronoi cells over "time". We set up a problem with 10 generators, with weights 1, 2, 3, ..., 10. We started with random initial locations for the generators, and carried out 100 iterations of the CVT code. We saved a PPMB file containing an image of each step, used the CJPEG program to convert these to JPEG files with consecutive file names, fed that into QuickTime Pro to create an animation, and saved the result as an MPEG-4 file.


The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.


CVT_FIXED is available in a FORTRAN90 version.

Related Data and Programs:

PPMB, a data format which is used for the images of the CVT regions.

PBMLIB, a FORTRAN90 library which is used to create the graphics files.


  1. Franz Aurenhammer,
    Voronoi diagrams - a study of a fundamental geometric data structure,
    ACM Computing Surveys,
    Volume 23, Number 3, pages 345-405, September 1991,
  2. John Burkardt, Max Gunzburger, Janet Peterson and Rebecca Brannon,
    User Manual and Supporting Information for Library of Codes for Centroidal Voronoi Placement and Associated Zeroth, First, and Second Moment Determination,
    Sandia National Laboratories Technical Report SAND2002-0099,
    February 2002.
  3. Qiang Du, Vance Faber, and Max Gunzburger,
    Centroidal Voronoi Tessellations: Applications and Algorithms,
    SIAM Review, Volume 41, 1999, pages 637-676.
  4. Lili Ju, Qiang Du, and Max Gunzburger,
    Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations,
    Parallel Computing,
    Volume 28, 2002, pages 1477-1500.

Source Code:

Examples and Tests:

List of Routines:

You can go up one level to the FORTRAN90 source codes.

Last revised on 12 November 2006.