jburkardt

LINE_CVT_LLOYD\ Lloyd’s CVT Method for a Line Segment {#line_cvt_lloyd-lloyds-cvt-method-for-a-line-segment align=”center”} =====================================


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: {#licensing align=”center”}

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

Languages: {#languages align=”center”}

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.

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: {#reference align=”center”}

  1. Qiang Du, Vance Faber, Max Gunzburger,\ Centroidal Voronoi Tessellations: Applications and Algorithms,\ SIAM Review, Volume 41, 1999, pages 637-676.

Source Code: {#source-code align=”center”}

Examples and Tests: {#examples-and-tests align=”center”}

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: {#list-of-routines align=”center”}

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


Last revised on 30 July 2014