LINE_CVT_LLOYD Lloyd's CVT Method for a Line Segment

LINE_CVT_LLOYD, a MATLAB library 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 programs 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 library which returns the points and weights of a Felippa quadrature rule over the interior of a line segment in 1D.

LINE_GRID, a MATLAB library 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.
• timestamp.m, prints the YMDHMS date as a timestamp.

Last revised on 14 February 2019.