LINE_CVT_LLOYD is a C 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.
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
LINE_CVT_LLOYD is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.
LINE_FELIPPA_RULE, a C library which returns the points and weights of a Felippa quadrature rule over the interior of a line segment in 1D.
LINE_GRID, a C library which computes a grid of points over the interior of a line segment in 1D.
TEST01 applies the unconstrained iteration, with random unsorted starting values.
TEST02 applies the constrained iteration, with random unsorted starting values.
TEST03 applies the unconstrained iteration, with random sorted starting values.
TEST04 applies the constrained iteration, with random sorted starting values.
You can go up one level to the C source codes.