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

### Examples and Tests:

RANDOM sets the random initial values, using 40 generators and 400 steps.

• random_energy.png a PNG image of the "energy" of the partition, which is the averaged sum of squares of the distances between each sample point and its nearest generator.
• random_evolution.png a PNG image of the evolution or trajectories of the generators as the iteration proceeds.
• random_motion.png a PNG image of the "motion" of the generators, which is the averaged distance each generator moves during an iteration.

SQUASHED sets the "squashed" initial values between 0.01 and 0.02, using 40 generators and 400 steps.

• squashed_energy.png a PNG image of the "energy" of the partition, which is the averaged sum of squares of the distances between each sample point and its nearest generator.
• squashed_evolution.png a PNG image of the evolution or trajectories of the generators as the iteration proceeds.
• squashed_motion.png a PNG image of the "motion" of the generators, which is the averaged distance each generator moves during an iteration.

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

Last revised on 15 September 2016.