CVT_CORN
Model Cell Growth in a Corn Kernel

CVT_CORN is a MATLAB program which studies a 2D model of the growth of a corn kernel.

The program treats 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.

Here are two photomicrographs of a radial slice and a transverse slice through a corn kernel. These pictures were an inspiration for the study done here.

The program models the corn kernel as a circle. There is a layer of surface cells on the circumference of the circle, and a collection of interior cells within the circle. Each cell is marked, that is, it knows what kind of cell it is, and this marker is never changed. Each cell is modeled by a single geometric point. The extent of a surface cell is the set of circumference points closer to it than to any other circumference cell. The extent of an interior cell is the set of interior points closer to it than to any other interior cell.

Cells may move. Surface cells may move along the circumference. Interior cells may move within the interior.

We presume that the cells adjust their positions in accordance with the energy minimization principle. Briefly, this means that each cell's preferred location is the centroid of its extent. Surface cells may only move to the projection of their centroid on the circumference.

If we move each cell to its centroid, the extent of the cell changes, and hence the centroid changes. An iteration can be carried out in which we compute centroids and move cells to their centroids. This iteration will in general approach what is known as a Centroidal Voronoi Tessellation (CVT).

By the specification of a nonuniform density function, the calculation of the centroid can be influenced in such a way that cells tend to cluster preferentially in certain regions. For the corn kernel, we can apply such a density function which will tend to push cells away from the circle center.

As a rough model of growth, once we have completed a CVT iteration, we may begin a new step by allowing cells to "bud". Surface and cells are each given a probability of budding. We then compute which cells have budded. Surface cells can give birth to another surface cell, or to an interior cell. Once the new cells have been created, and positioned very close to their parents, another CVT iteration is carried out.

The program uses some parameters which the user can monitor or set:

• ALG, the CVT update algorithm:
  • 1 = update circle + disk together.
  • 2 = update circle only, then update disk only.
  • 3 = update circle only, then update circle + disk together.
• NB, the number of points on boundary;
• NI, number of point in interior;
• NP, total number of points;
• NS, number of sample points for Lloyd's algorithm;
• PR_BUD, probability that a boundary point will create a bud;
• PR_BUD_ANGULAR, probability that boundary bud is constrained to the boundary;
• R, the radius of the circle;
• SEED, the initial random number seed;

Licensing:

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

Languages

CVT_CORN is available in a MATLAB version.

Related Data and Programs:

CVT, a MATLAB library which can compute a 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.

CVT_1D_NONUNIFORM, a MATLAB program which constructs a CVT in one dimension, under a nonuniform density function.

CVT_1D_SAMPLING, a MATLAB program 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 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_CIRCLE_UNIFORM, a MATLAB program which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with uniform density.

CVT_DEMO, a MATLAB program which is an interactive graphic demonstration of 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.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, pages 345-405, September 1991.
2. John Burkardt, Max Gunzburger, Janet Peterson, Rebecca Brannon,
   User Manual and Supporting Information for Library of Codes for Centroidal Voronoi Placement and Associated Zeroth, First, and Second Moment Determination,
   Sandia National Laboratories Technical Report SAND2002-0099,
   February 2002.
3. Qiang Du, Vance Faber, Max Gunzburger,
   Centroidal Voronoi Tessellations: Applications and Algorithms,
   SIAM Review,
   Volume 41, 1999, pages 637-676.
4. Lili Ju, Qiang Du, Max Gunzburger,
   Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations,
   Parallel Computing,
   Volume 28, 2002, pages 1477-1500.

Source Code:

• bud.m, carries out the budding process.
• bud_angular.m, sets the coordinates for an "angular" bud.
• bud_radial.m, sets the coordinates for a "radial" bud.
• cvt_circle.m, applies the CVT algorithm to points on a circle.
• cvt_circle_step.m, applies one step of the CVT algorithm to points on a circle.
• cvt_corn.m, the main program, which carries out the simulation of the growth of a kernel of corn.
• cvt_disk.m, computes a CVT in the disk.
• cvt_disk_interior.m, computes a CVT in the disk interior.
• cvt_display.m, displays the estimated CVT diagram.
• disk_sample_nonuniform.m, nonuniformly samples the disk of radius R.
• disk_sample_uniform.m, uniformly samples the disk of radius R.
• find_closest.m, finds the nearest G point to each S point.
• goodbye.m, issues a final message to the user.
• hello.m, issues an initial message to the user.
• parameter_initialize.m, sets the initial values of parameters.
• parameter_print.m, prints the current values of parameters
• parameter_set.m, allows the user to reset parameter values.
• r8_atan.m, computes the inverse tangent of the ratio Y / X.
• r8mat_transpose_print.m, prints an R8MAT, transposed.
• r8mat_transpose_print_some.m, prints some of an R8MAT, transposed.
• radial_growth.m, simulates the radial expansion of the region.
• state_display.m, displays the current state.
• state_initialize.m, initializes the state.
• timestamp.m, prints the current YMDHMS date as a timestamp.

Examples and Tests:

The following images are snapshots from a run of the program with the default parameter settings:

• initial.png, the initial random state, with 40 boundary points and 60 interior points.
• step00.png, the CVT at step 0.
• step01.png, the CVT at step 1.
• step02.png, the CVT at step 2.
• step03.png, the CVT at step 3.
• step04.png, the CVT at step 4
• step05.png, the CVT at step 5.
• step10.png, the CVT at step 10.
• step20.png, the CVT at step 20.
• step30.png, the CVT at step 30.

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