CVT_1D_LLOYD
Centroidal Voronoi Tessellation in [0,1]


CVT_1D_LLOYD is a MATLAB program which allows the user to carry out Lloyd's algorithm for a Centroidal Voronoi Tessellation (CVT) in the interval [0,1].

The determination of the Voronoi regions is carried out using exact techniques.

For n generators, the solution is known in advance:

x(i) = ( 2 * i - 1 ) / ( 2 * n )
Lloyd's iterative algorithm starts from an arbitrary vector x, however, so it is interesting to see how the approximate solution evolves toward the correct answer.

Usage:

cvt_1d_lloyd ( n, it_num, init )
where

Licensing:

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

Languages:

CVT_1D_LLOYD is available in a MATLAB version and a Python version.

Related Data and Programs:

CCVT_BOX, a MATLAB program which constructs a constrained Centroidal Voronoi Tessellation (CCVT) in which some points are forced to lie on the boundary.

CCVT_REFLECT, a MATLAB program which tries to construct a constrained Centroidal Voronoi Tessellation (CCVT) in which some points are forced to lie on the boundary, using a reflection idea.

CVT, a MATLAB library which computes a Centroidal Voronoi Tessellation (CVT).

CVT, a dataset directory which contains a variety of examples of Centroidal Voronoi Tessellations (CVT).

cvt_1d_lloyd_test

CVT_1D_NONUNIFORM, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) in 1 dimension, under a nonuniform density, and plots the evolution of the locations of the generators during the iteration;

CVT_1D_SAMPLING, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the interval [0,1], under a uniform density, using sampling to estimate the Voronoi regions.

CVT_2D_SAMPLING, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the unit square [0,1]x[0,1], under a uniform density, using sampling to estimate the Voronoi regions.

CVT_3D_SAMPLING, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the unit cube [0,1]x[0,1]x[0,1], under a uniform density, using sampling to estimate the Voronoi regions.

CVT_CIRCLE_UNIFORM, a MATLAB program which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with uniform density.

CVT_DATASET, a MATLAB program which can create a Centroidal Voronoi Tessellation (CVT) dataset.

CVTM_1D, a MATLAB program which estimates a mirror-periodic Centroidal Voronoi Tessellation (CVTM) in the periodic interval [0,1], using a version of Lloyd's iteration.

LCVT, a MATLAB library which computes a "Latinized" Centroidal Voronoi Tessellation (CVT).

Reference:

  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. Qiang Du, Vance Faber, Max Gunzburger,
    Centroidal Voronoi Tessellations: Applications and Algorithms,
    SIAM Review, Volume 41, 1999, pages 637-676.

Source Code:


Last revised on 23 December 2018.