# cvt_1d_lumping

cvt_1d_lumping, a MATLAB code 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 interval [-1,+1], for a general density function rho(x). This code has been applied to investigate a relationship between CVT's and the Chebyshev Zero nodes.

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), although the density function rho(x) 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]) and the density function rho(x).

The lumped version of Lloyd's iteration begins with 0an initial guess for the values G. Then the interval [-1,+1] is sampled by selecting S_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 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
```

This suggests that, if we take the Chebyshev Zero density mu(x), cube it to get a CVT density rho(x), then the corresponding CVT generators g(i) will asymptotically satisfy:

```        h(i)^3 * rho(g(i))   approximately constant;
h(i)^3 *  mu(g(i))^3 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.

To investigate this hypothesis, we compute a sequence of CVT generators of orders N = 3, 5, 9, 17, 33, 65, 129, 257, and tabulate the values of rho(g(i)*h(i)^3 and mu(g(i))*h, while making a similar table for the Chebyshev Zero nodes.

### Usage:

cvt_1d_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 may 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 1,000 and 100,000 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)^3. 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_1d_lumping is available in a MATLAB version.

### Related Data and Programs:

ccvt_reflect, a MATLAB code 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 code 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 code 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_nonuniform, a MATLAB code 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_1d_sampling, a MATLAB code which computes an N-point Centroidal Voronoi Tessellation (CVT) within the interval [0,1], under a uniform density, using sampling to estimate the Voronoi regions.

cvt_2d_sampling, a MATLAB code 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 code 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 code which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with nonuniform density.

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

cvt_corn, a MATLAB code 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.

cvtm_1d, a MATLAB code 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 code which estimates a periodic centroidal Voronoi Tessellation (CVTP) in the periodic interval [0,1], using a version of Lloyd's iteration.

florida_cvt_geo, a MATLAB code which explores the creation of a centroidal Voronoi Tessellation (CVT) of the state of Florida, based solely on geometric considerations.

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

### Source Code:

• mu_chebyzero.m, returns the mu(x) density for the Chebyshev Zero nodes.
• cvt_1d_lumping.m, computes a CVT in [-1,+1] with N generators, using IT_NUM iterations, S_NUM sample points, and a given MU density function.

Last revised on 24 December 2018.