# CVT_3D_LUMPING Lumped Version of Lloyd's Algorithm in the Cube

CVT_3D_LUMPING is a MATLAB program which allows the user to carry out a lumped version of Lloyd's iterative algorithm for the computation of a centroidal Voronoi Tessellation (CVT) in the unit cube [-1,+1]^3, for a general density function rho(x,y,z).

Typically, Lloyd's algorithm is carried out using simple sampling, that is, some procedure is available for producing a sequence of points uniformly at random with respect to the density function rho(x,y,z), although the density function rho(x,y,z) might not itself be known. In lumping, the density function is known, and so the geometric region is uniformly sampled, and each sample point s is given a weight rho(s). These weighted samples are more efficient in making the influence of the density function apparent in the calculation, although in the limit, lumped sampling and simple sampling will be equivalent.

The purpose of Lloyd's algorithm is to determine the location of N "generators" G in a geometric region, such that each g(i) is the density-weighted centroid of the set of points closer to g(i) than to any other generator. Such a set G is termed a Centroidal Voronoi Tessellation with respect to the region (here [-1,+1]^3) and the density function rho(x,y,z).

The lumped version of Lloyd's iteration begins with an initial guess for the values G. Then the cube is sampled by selecting a grid of S_NxS_NxS_N equally spaced points S, at which the density is evaluated. Each g(i) in G is replaced by the density-weighted average of all the sample points s whose closest generator is g(i). This process is repeated a given number of times, or until the set G seems to have converged.

The code presented here has been specifically adapted to investigate a particular question more specifically, namely, whether a CVT iteration can be induced to ``discover'' the set C of Chebyshev Zero nodes (Trefethen's terminology), whose elements are:

```        c(i) = cos ( ( 2 * n + 1 - 2 * i ) / 2 / n ), 1 <= i <= n.
```
by the appropriate choice of a density function rho(x). It is known that the Chebyshev Zero nodes are distributed asymptotically according to a density mu(x) that has the form:
```        mu(x) = 1 / sqrt(1-x^2) / pi.
```
Further, if h(i) is the width of the interval around c(i), which might be taken to be, in general (c(i+1)-c(i-1))/2, we have in general that:
```        h(i) * mu(c(i)) approximately constant.
```

The reference Du, Faber and Gunzburger shows that asymptotically, the 1D CVT generators g(i) and their spacings h(i), which may be taken to be (g(i+1)-g(i-1))/2, satisfy

```        h(i)^3 * rho(g(i)) approximately constant
```

For the 3D case, the corresponding relationship is CVT generators g(i) will asymptotically satisfy:

```        h(i)^5 * rho(g(i))   approximately constant;
h(i)^5 *  mu(g(i))^5 approximately constant;
h(i)   *  mu(g(i))   approximately constant,
```
suggesting that the generators g(i) may tend to the locations of the Chebyshev Zero nodes.

### Usage:

cvt_3d_lumping ( n, it_num, s_num, @ mu )
where
• n is the number of generators; because the Chebyshev Zero nodes are an interestting comparison set, and they are nested, it is natural to look at n = 3, 5, 9, 17, ..., 2^k+1.
• it_num is the number of iterative steps to take. A value of 250 is a reasonable guess. You can judge whether the generators have come close to their final positions by looking at the evolution plot and seeing if the curves have become essentially vertical at the end.
• s_num is the number of sample points. A value between 100 and 1000 is typical.
• @ mu is the name of an M file which evaluates the mu(x) density function. The rho(x) density function needed for the CVT iteratgion is determined by computing rho(x)=mu(x)^5. For this program, the only density function examined is that associated with the Chebyshev Zero nodes, mu(x)=1/sqrt(1-x^2), available in the file mu_chebyzero.m.

### Languages:

CVT_3D_LUMPING is available in a MATLAB version.

### Related Data and Programs:

CCL, a MATLAB program which estimates the Lebesgue constants for sets of points in [-1,+1] computed in several ways. The program is probably of limited interest except as an example of an application of the lebesgue_constant() function.

CCVT_BOX, a MATLAB program which constructs a modified CVT in which some points are forced to lie on the boundary.

CCVT_REFLECT, a MATLAB program which tries to construct a modified CVT in which some points are forced to lie on the boundary, using a reflection idea.

CVT, a MATLAB library which computes elements of a Centroidal Voronoi Tessellation (CVT).

CVT, a dataset directory which contains a variety of examples of CVT datasets.

CVT_1D_LLOYD, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the interval [0,1], under a uniform density, using exact techniques to determine the Voronoi regions.

CVT_1D_LUMPING, a MATLAB program which allows the user to carry out a lumped version of Lloyd's iterative algorithm for a centroidal Voronoi Tessellation (CVT() in the interval [-1,+1], and is applied to investigate a relationship between CVT's and the Chebyshev Zero nodes.

CVT_1D_NONUNIFORM, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation in 1 dimension, under a nonuniform density, and plots the evolution of the locations of the generators during the iteration;

CVT_2D_LUMPING, a MATLAB program which allows the user to carry out a lumped version of Lloyd's iterative algorithm for a centroidal Voronoi Tessellation (CVT() in the square [-1,+1]^2, and is applied to investigate a relationship between CVT's and the Chebyshev Zero nodes.

CVT_2D_SAMPLING, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the unit square [0,1]x[0,1], under a uniform density, using sampling to estimate the Voronoi regions.

CVT_3D_SAMPLING, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the unit cube [0,1]x[0,1]x[0,1], under a uniform density, using sampling to estimate the Voronoi regions.

CVT_CIRCLE_NONUNIFORM, a MATLAB program which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with nonuniform density.

CVT_CIRCLE_UNIFORM, a MATLAB program which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with uniform density.

CVT_CORN, a MATLAB program which studies a 2D model of the growth of a corn kernel, by treating the surface and interior biological cells as points to be organized by a Centroidal Voronoi Tessellation (CVT) with a nonuniform density; during a sequence of growth steps, new biological cells are randomly added to the surface and interior.

CVT_DATASET, a MATLAB program which can create a CVT dataset.

CVT_DEMO, a MATLAB program which demonstrates a CVT calculation.

CVTM_1D, a MATLAB program which estimates a mirror-periodic centroidal Voronoi Tessellation (CVTM) in the periodic interval [0,1], using a version of Lloyd's iteration.

CVTP_1D, a MATLAB program which estimates a periodic centroidal Voronoi Tessellation (CVTP) in the periodic interval [0,1], using a version of Lloyd's iteration.

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.

LCVT, a MATLAB library which computes a "Latinized" Centroidal Voronoi Tessellation.

### Reference:

1. Qiang Du, Vance Faber, Max Gunzburger,
Centroidal Voronoi Tessellations: Applications and Algorithms,
SIAM Review, Volume 41, 1999, pages 637-676.
2. Lloyd Trefethen,
Spectral Methods in MATLAB,
SIAM, 2000,
ISBN: 0898714656,
LC: QA377.T65.

### Examples and Tests:

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

Last revised on 17 October 2016.