cvt_3d_lumping, an Octave 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 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.
cvt_3d_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_3d_lumping is available in a MATLAB version and an Octave version.
CCL, an Octave 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, an Octave program which constructs a modified CVT in which some points are forced to lie on the boundary.
CCVT_REFLECT, an Octave program which tries to construct a modified CVT in which some points are forced to lie on the boundary, using a reflection idea.
CVT, an Octave 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, an Octave 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, an Octave 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, an Octave 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, an Octave 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, an Octave 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, an Octave 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, an Octave program which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with nonuniform density.
CVT_CIRCLE_UNIFORM, an Octave program which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with uniform density.
CVT_CORN, an Octave 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, an Octave program which can create a CVT dataset.
CVT_DEMO, an Octave program which demonstrates a CVT calculation.
CVTM_1D, an Octave 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, an Octave 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, an Octave library which computes a "Latinized" Centroidal Voronoi Tessellation.