cvt_1d_sampling


cvt_1d_sampling, a MATLAB code which allows the user to carry out Lloyd's algorithm for a centroidal Voronoi Tessellation in the interval [0,1].

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, the solution is known in advance:

x(i) = ( 2 * i - 1 ) / ( 2 * n )
Lloyd's algorithm starts from an arbitrary vector x, however, so it is interesting to see how the approximate solution evolves toward the correct answer.

Usage:

cvt_1d_sampling ( n, it_num, sample_num )
where

Licensing:

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

Languages:

cvt_1d_sampling is available in a MATLAB version.

Related Data and Programs:

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 exact techniques to determine the voronoi regions.

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_test

cvt_2d_nonuniform, 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_nonuniform, 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_uniform, a MATLAB code which calculates a centroidal voronoi tessellation (cvt) over a circle with uniform density.

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_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.

florida_cvt_geo, a MATLAB code which explores 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 24 December 2018.