cvt_1d_lloyd
cvt_1d_lloyd,
a Python code which
allows the user to carry out Lloyd's algorithm for a
Centroidal Voronoi Tessellation (CVT) in the interval [0,1].
The determination of the Voronoi regions is carried out using
exact techniques.
For n generators, the solution is known in advance:
x(i) = ( 2 * i - 1 ) / ( 2 * n )
Lloyd's iterative 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_lloyd ( n, it_num, init, prefix )
where
-
n is the number of generators;
-
it_num is the number of iterative steps to take.
-
init is 0 for random initialization, 1 for a "squashed" in which the
starting values are confined to a small region.
-
prefix is a string such as 'random_' or 'squashed_' which is
used to name the energy, motion, and evolution graphics files.
Licensing:
The computer code and data files described and made available on this web page
are distributed under
the MIT license
Languages:
cvt_1d_lloyd is available in
a MATLAB version and
a Python version.
Related Data and Programs:
cvt_2d_sampling,
a Python 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.
florida_cvt_geo,
a Python code which
creates a centroidal Voronoi Tessellation (CVT) of
the state of Florida, based solely on geometric considerations.
florida_cvt_pop,
a Python code which
creates a centroidal Voronoi Tessellation (CVT) of
the state of Florida, based on population density.
Reference:
-
Franz Aurenhammer,
Voronoi diagrams -
a study of a fundamental geometric data structure,
ACM Computing Surveys,
Volume 23, Number 3, pages 345-405, September 1991.
-
Qiang Du, Vance Faber, Max Gunzburger,
Centroidal Voronoi Tessellations: Applications and Algorithms,
SIAM Review, Volume 41, 1999, pages 637-676.
Source Code:
RANDOM sets the random initial values,
using 40 generators and 400 steps.
-
random_energy.png
a PNG image of the "energy" of the partition, which is the averaged
sum of squares of the distances between each sample point and its
nearest generator.
-
random_evolution.png
a PNG image of the evolution or trajectories of the generators as the
iteration proceeds.
-
random_motion.png
a PNG image of the "motion" of the generators, which is the averaged
distance each generator moves during an iteration.
SQUASHED sets the "squashed" initial values between 0.01 and 0.02,
using 40 generators and 400 steps.
-
squashed_energy.png
a PNG image of the "energy" of the partition, which is the averaged
sum of squares of the distances between each sample point and its
nearest generator.
-
squashed_evolution.png
a PNG image of the evolution or trajectories of the generators as the
iteration proceeds.
-
squashed_motion.png
a PNG image of the "motion" of the generators, which is the averaged
distance each generator moves during an iteration.
Last revised on 16 September 2016.