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

Source Code:

• line_cvt_lloyd.c, the source code.
• line_cvt_lloyd.h, the include file.
• line_cvt_lloyd.sh, BASH commands to compile the source code.

Examples and Tests:

• line_cvt_lloyd_prb.c, a sample calling program.
• line_cvt_lloyd_prb.sh, BASH commands to compile and run the sample program.
• line_cvt_lloyd_prb_output.txt, the output file.

TEST01 applies the unconstrained iteration, with random unsorted starting values.

• test01_energy_commands.txt GNUPLOT commands to create a plot.
• test01_energy_data.txt data needed to create a plot.
• test01_energy.png a PNG image of the "energy" of the partition.
• test01_evolution_commands.txt GNUPLOT commands to create a plot.
• test01_evolution_data.txt data needed to create a plot.
• test01_evolution.png a PNG image of the evolution of the generators.
• test01_motion_commands.txt GNUPLOT commands to create a plot.
• test01_motion_data.txt data needed to create a plot.
• test01_motion.png a PNG image of the "motion" of the generators.

TEST02 applies the constrained iteration, with random unsorted starting values.

• test02_energy_commands.txt GNUPLOT commands to create a plot.
• test02_energy_data.txt data needed to create a plot.
• test02_energy.png a PNG image of the "energy" of the partition.
• test02_evolution_commands.txt GNUPLOT commands to create a plot.
• test02_evolution_data.txt data needed to create a plot.
• test02_evolution.png a PNG image of the evolution of the generators.
• test02_motion_commands.txt GNUPLOT commands to create a plot.
• test02_motion_data.txt data needed to create a plot.
• test02_motion.png a PNG image of the "motion" of the generators.

TEST03 applies the unconstrained iteration, with random sorted starting values.

• test03_energy_commands.txt GNUPLOT commands to create a plot.
• test03_energy_data.txt data needed to create a plot.
• test03_energy.png a PNG image of the "energy" of the partition.
• test03_evolution_commands.txt GNUPLOT commands to create a plot.
• test03_evolution_data.txt data needed to create a plot.
• test03_evolution.png a PNG image of the evolution of the generators.
• test03_motion_commands.txt GNUPLOT commands to create a plot.
• test03_motion_data.txt data needed to create a plot.
• test03_motion.png a PNG image of the "motion" of the generators.

TEST04 applies the constrained iteration, with random sorted starting values.

• test04_energy_commands.txt GNUPLOT commands to create a plot.
• test04_energy_data.txt data needed to create a plot.
• test04_energy.png a PNG image of the "energy" of the partition.
• test04_evolution_commands.txt GNUPLOT commands to create a plot.
• test04_evolution_data.txt data needed to create a plot.
• test04_evolution.png a PNG image of the evolution of the generators.
• test04_motion_commands.txt GNUPLOT commands to create a plot.
• test04_motion_data.txt data needed to create a plot.
• test04_motion.png a PNG image of the "motion" of the generators.

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.