# 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
• n is the number of generators;
• it_num is the number of iterative steps to take.
• init is 0 for random initialization, 1 for a "squashed" in which the starting values are confined to a small region.

### 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_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.