# cvtp_1d

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.

The determination of the Voronoi regions is carried out using sampling. This means that the convergence of the iteration is influenced by the accuracy of the estimates provided by sampling.

For n generators, a solution set is known in advance:

x(i) = i / n, i = 1 : n
as is any periodic translate of this set. Lloyd's algorithm starts from an arbitrary vector x, however, so it is interesting to see how the approximate solution evolves toward a correct solution, whose fundamental property is that the generators are equally spaced within the periodic domain.

### Usage:

cvtp_1d ( g_num, it_num, sample_num )
where
• g_num is the number of generators (try 10 to start);
• it_num is the number of iterative steps to take (try 10 initially).
• sample_num is the number of sample points in [0,1] used to estimate the Voronoi regions. (A value between 1,000 and 10,000 is typical).

### Languages:

cvtp_1d is available in a MATLAB version.

### Related Data and Programs:

cvt_box, a MATLAB code which constructs a modified cvt in which some points are forced to lie on the boundary.

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 cvt's.

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 lloyd's method to compute the voronoi regions exactly.

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 nonuniform centroidal voronoi tessellation (cvt) over a circle.

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.

cvt_ellipse_uniform, a MATLAB code which iteratively calculates a centroidal voronoi tessellation (cvt) over an ellipse, with a uniform density.

cvt_metric, a MATLAB code which computes a centroidal voronoi tessellation (cvt) under a spatially varying metric;

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, a MATLAB code which creates a cvtp, that is, a centroidal voronoi tessellation on a periodic domain.

florida_cvt_geo, MATLAB codes 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. Qiang Du, Vance Faber, Max Gunzburger,
Centroidal Voronoi Tessellations: Applications and Algorithms,
SIAM Review, Volume 41, 1999, pages 637-676.

### Source Code:

Last revised on 15 December 2018.