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.

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:

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.

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:

• ENERGY_PLOT plots the energy as a function of the iterations.
• EVOLUTION_PLOT plots all points as a function of the iterations.
• LINE_CCVT_LLOYD carries out the constrained Lloyd algorithm.
• LINE_CCVT_LLOYD_STEP takes one step of Lloyd's constrained CVT algorithm.
• LINE_CVT_ENERGY computes the CVT energy for a given set of generators.
• LINE_CVT_LLOYD carries out the Lloyd algorithm.
• LINE_CVT_LLOYD_STEP takes one step of Lloyd's unconstrained CVT algorithm.
• MOTION_PLOT plots the motion as a function of the iterations.
• R8VEC_PRINT prints an R8VEC.
• R8VEC_SORT_INSERT_A ascending sorts an R8VEC using an insertion sort.
• R8VEC_UNIFORM_AB returns a scaled pseudorandom R8VEC.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

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

Last revised on 30 July 2014