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.


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


  1. 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 14 February 2019.