CVT_2D_LUMPING, 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 square [-1,+1]x[-1,+1], for a general density function rho(x,y).
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), although the density function rho(x,y) 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]x[-1,+1]) and the density function rho(x,y).
The lumped version of Lloyd's iteration begins with an initial guess for the values G. Then the square [-1,+1]x[-1,+1] is sampled by selecting a grid of S_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 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.
cvt_2d_lumping ( n, it_num, s_num, @ mu )where
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
CVT_2D_LUMPING is available in a MATLAB version.
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_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.
CVT_SQUARE_NONUNIFORM, a MATLAB program which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over a square, with a nonuniform density.
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.