cvt_corn


cvt_corn, an Octave code which studies a 2D model of the growth of a corn kernel.

Scientists understand the basic physical laws that govern the chemical reactions involved in the growth of a cell. However, they are still searching for models that can suggest the phenomena observed as a collection of cells grow into an organism. Simple observations are that the cells take on a convex polygonal shape, that neighboring cells share a flattened boundary, that the nucleus of each cell stays roughly in the center, that the growth rate of cells can vary in proportion to the distance from some growth center, and that the organism tends to have an outer layer of cells that form a boundary or skin.

A suggested model comes from the Voronoi diagram. The Voronoi diagram starts with a plane, and a set of points, and divides a finite portion of the plane by drawing a boundary line around each point, enclosing all the territory that is closest to it. While the Voronoi diagram organizes the plane, there may be a great irregularity in the size and shape of the regions, and most points will not be centrally located in their regions.

A variation of the Voronoi diagram is known as the Centroidal Voronoi Tessellation or CVT. The CVT assumes that the points have some kind of tendency to move towards the center of their regions. If the points move, then the regions will change shape, which will impel the points to move a little more. This dynamic process actually will come to a conclusion, in which every point is exactly in the center of its region, and the regions are all roughly the same size and shape. The image of a CVT can strongly suggest a biological structure such as a slice through a honeycomb.

Two modifications to the CVT idea help us to improve our simulation. By adding a weight function, we can allow a smooth variation in the size of the regions; in this case, we expect larger cells in the center of the corn kernel, and smaller ones as we go outward. It is also possible to modify the CVT idea so that some points, however reluctantly, are pushed to form a smooth boundary, whereas in a pure CVT, no points would appear there.

This means that we can try to adjust a CVT to model the development of a simple biological organism. Although the CVT can handle problems in 3D, we will look at a simplified 2D case; we can imagine we are viewing a slice of a real object as it grows.

The program cvt_corn.m demonstrates some of these ideas by ``growing'' a simulated corn kernel, which starts out as a circular area containing cells, randomly placed in the interior and on the boundary. The program simulates growth by applying the CVT algorithm with a nonuniform density, adjusting the boundary layer, and also randomly adding new biological cells at each step. As the number of cells increase, the corn seed is also allowed to grow in size, while staying circular.

Since we don't have much data to work with, we are free to choose such quantities as the nonuniformity function, the number and initial placement of cells, the rate of growth. What we are looking for is ``phenomenology'', that is, can our process make pictures that roughly correspond to what is seen in nature?

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.

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:

Licensing:

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

Languages

cvt_corn is available in a MATLAB version and an Octave version.

Related Data and Programs:

cvt_corn_test

cvt, an Octave code which can compute a CVT.

cvt_1d_lloyd, an Octave code which computes an N-point Centroidal Voronoi Tessellation (CVT) within the interval [0,1], under a uniform density.

cvt_1d_nonuniform, an Octave code which constructs a CVT in one dimension, under a nonuniform density function.

cvt_1d_sampling, an Octave 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, an Octave 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_circle_uniform, an Octave code which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with uniform density.

cvt_corn_movie, an Octave code which makes a movie in which the growth of a corn kernel is simulated using a Centroidal Voronoi Tessellation (CVT).

cvt_square_nonuniform, an Octave code which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over a square, with a nonuniform density.

cvtm_1d, an Octave 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, an Octave 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, an Octave code which explore the creation of a centroidal Voronoi Tessellation (CVT) of the state of Florida, based solely on geometric considerations.

florida_cvt_pop, an Octave code which explore the creation of a centroidal Voronoi Tessellation (CVT) of the state of Florida, based on population density.

usa_cvt_geo, MATLAB codes which explore the creation of a centroidal Voronoi Tessellation (CVT) of the United States, 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. Qiang Du, Vance Faber, Max Gunzburger,
    Centroidal Voronoi Tessellations: Applications and Algorithms,
    SIAM Review,
    Volume 41, 1999, pages 637-676.
  3. 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:

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


Last revised on 20 July 2023.