LINE_CVT_LLOYD
Lloyd's CVT Method for a Line Segment


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.

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 FORTRAN90 version and a MATLAB version.

Related Data and Programs:

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.

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.

List of Routines:

You can go up one level to the C source codes.


Last revised on 30 July 2014