LINE_CVT_LLOYD
Lloyd's CVT Method for a Line Segment


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

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

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.

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:

Examples and Tests:

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 MATLAB source codes.


Last revised on 28 July 2014