cvt_basis, a FORTRAN90 code which uses discrete Centroidal Voronoi Tessellation (CVT) techniques to produce a small set of basis vectors that are good cluster centers for a large set of data vectors;

The clustering process uses the K-Means algorithm, which can be considered to be a discrete version of the CVT algorithm.

The data is a collection of vectors, with each vector stored in a separate file. The files are presumed to have "sequential" names, such as "fred01.txt", "fred02.txt", and so on. Each file must be a TABLE file, that is a series of N lines, with M values on every line (although comment lines may be inserted as well.)

The code is given the name of the first file in the sequence. It reads the data from each file in the sequence, and carries out the K Means clustering process to determine K cluster centers. It writes each of these cluster centers out to a separate file.

The cluster centers will generally be "well spread out" in the space spanned by the set of data. Such a set might be useful, for instance, in determining a basis for a low-dimensional approximation of the data.

INPUT: at run time, the user specifies:


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


cvt_basis is available in a FORTRAN90 version.

Related Data and codes:


brain_sensor_pod, a MATLAB code which applies the method of Proper Orthogonal Decomposition to seek underlying patterns in sets of 40 sensor readings of brain activity.

burgers, a data set directory which contains solutions of the 1 dimensional Burgers equation;

cavity_flow, a dataset directory which contains solutions of a driven cavity flow in 2D;

cvt_basis_flow, a FORTRAN90 code which is similar to CVT_BASIS, but is specialized to handle a particular family of fluid flow solutions.

cvtp, a FORTRAN90 code which creates a CVTP, that is, a Centroidal Voronoi Tessellation on a periodic domain.

inout_flow, a dataset directory which contains solutions for flow in and out of a chamber in 2D;

inout_flow2, a dataset directory which contains solutions for flow in and out of a chamber in 2D, using a finer grid and more timesteps;

svd_basis, a FORTRAN90 code which uses the singular value decomposition to extract representative modes from a set of data vectors.

tcell_flow, a dataset directory which contains solutions for flow through a T-cell in 2D;


  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, Hyung-Chun Lee,
    Centroidal Voronoi Tessellation-Based Reduced-Order Modelling of Complex Systems,
    SIAM Journal on Scientific Computing,
    Volume 28, Number 2, 2006, pages 459-484.
  3. John Burkardt, Max Gunzburger, Janet Peterson, 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.
  4. Qiang Du, Vance Faber, Max Gunzburger,
    Centroidal Voronoi Tessellations: Applications and Algorithms,
    SIAM Review, Volume 41, 1999, pages 637-676.
  5. Lili Ju, Qiang Du, Max Gunzburger,
    Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations,
    Parallel Computing,
    Volume 28, 2002, pages 1477-1500.
  6. Wendy Martinez, Angel Martinez,
    Computational Statistics Handbook with MATLAB,
    Chapman and Hall / CRC, 2002.

Source Code:

Last revised on 30 April 2022.