# cvt_1d_lloyd

cvt_1d_lloyd, a MATLAB code 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_reflect, a MATLAB code 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 code 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 code 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 code 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 code 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 code 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 code which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with uniform density.

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

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