# line_cvt_lloyd

line_cvt_lloyd, a MATLAB code which carries out Lloyd's iteration for computing a Centroidal Voronoi Tesselation (CVT) of points over the interior of a line segment in 1D.

A constraint has been added to the computation, which forces the first and last points to be fixed to the endpoints of the line segment. This is not actually a requirement for Lloyd's method.

At least for the uniform density case, the exact solution of this problem is known in advance, and is simply a set of equally spaced points. For instance, for N = 4, the solution over the interval [0,1] would be 0, 1/3, 2/3, 1, if the endpoint constraint is imposed. If the endpoint constraint is NOT imposed, then the exact solution is: 1/8, 3/8, 5/8, 7/8.

### Languages:

line_cvt_lloyd is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.

### Related Data and Programs:

florida_cvt_geo, MATLAB codes which explore the creation of a centroidal Voronoi Tessellation (CVT) of the state of Florida, based solely on geometric considerations.

line_felippa_rule, a MATLAB code which returns the points and weights of a Felippa quadrature rule over the interior of a line segment in 1D.

line_grid, a MATLAB code which computes a grid of points over the interior of a line segment in 1D.

### Reference:

1. Qiang Du, Vance Faber, Max Gunzburger,
Centroidal Voronoi Tessellations: Applications and Algorithms,
SIAM Review, Volume 41, 1999, pages 637-676.

### Source Code:

• line_ccvt_lloyd.m, iterates Lloyd's CVT method for points on a line segment, with the first and last points constrained to equal the end values.
• line_ccvt_lloyd_step.m, takes one step of Lloyd's CVT method for points on a line segment, with the first and last points constrained to equal the end values.
• line_cvt_energy.m, evaluates an energy function which is reduced by each step of Lloyd's iteration.
• line_cvt_lloyd.m, iterates Lloyd's CVT method for points on a line segment.
• line_cvt_lloyd_step.m, takes one step of Lloyd's CVT method for points on a line segment.

Last revised on 14 February 2019.