LCVT
Latin Centroidal Voronoi Tessellations

LCVT, a MATLAB library which creates Latin Centroidal Voronoi Tessellation (CVT) datasets.

A Latin Square dataset is typically a two dimensional dataset of N points in the unit square, with the property that, if both the x and y axes are divided up into N equal subintervals, exactly one dataset point has an x or y coordinate in each subinterval. Latin squares can easily be extended to the case of M dimensions, and may be pedantically called "Latin Hypersquares" or "Latin Hypercubes" in such a case. Statisticians like Latin Squares, as do experiment designers, and and people who need to approximate scalar functions of many variables.

The fact that the projection of a Latin Square dataset onto any coordinate axis is either exactly evenly spaced, or approximately so (depending on the algorithm), turns out to be an attractive feature for many uses.

However, a CVT dataset in a regular domain, such as the unit hypercube, has the tendency for the projections of the points to cluster together in any coordinate axis. This program is mainly an attempt to explore whether a dataset can be computed using techniques similar to those of a CVT, but with the constraint (whether imposed or expected) that the point projections do not clump up.

The approach used here is quite simple. First we compute a CVT in M dimensions, comprising N points. We assume that the bounding region is the unit hypercube. We are now going to adjust the coordinates of the points to achieve the Latin Hypercube property. For each coordinate direction, we simply sort the points by that coordinate, and then overwrite the original values by the values we'd expect to get for a centered Latin Hypercube, namely, 1/(2*N), 3/(2*N), ..., (2*N-1)/(2*N).

Now this process guarantees that we get a Latin Hypercube. Our hope is that the process of adjusting the point coordinates does not too severely damage the nice dispersion properties inherent in the CVT point placement.

Licensing:

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

Languages:

LCVT is available in a C++ version and a FORTRAN90 version and a MATLAB version

Related Data and Programs:

CVT, a MATLAB library which computes a Centroidal Voronoi Tessellation.

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

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.

GRID, a MATLAB library which computes elements of a grid dataset.

HALTON, a MATLAB library which computes elements of a Halton quasirandom sequence.

HAMMERSLEY, a MATLAB library which computes elements of a Hammersley quasirandom sequence.

IHS, a MATLAB library which computes elements of an improved distributed Latin hypercube dataset.

LATIN_CENTER, a MATLAB library which computes elements of a Latin Hypercube dataset, choosing center points.

LATIN_EDGE, a MATLAB library which computes elements of a Latin Hypercube dataset, choosing edge points.

LATIN_RANDOM, a MATLAB library which computes elements of a Latin Hypercube dataset, choosing points at random.

LATINIZE, a MATLAB program which can "latinize" a dataset.

LATTICE_RULE, a MATLAB library which approximates multidimensional integrals using lattice rules.

lcvt_test

LCVT_DATASET, a directory which contains a collection of sample LCVT datasets.

NIEDERREITER2, a MATLAB library which computes elements of a Niederreiter quasirandom sequence with base 2.

NORMAL, a MATLAB library which computes elements of a normal pseudorandom sequence.

SOBOL, a MATLAB library which computes elements of a Sobol quasirandom sequence.

UNIFORM, a MATLAB library which computes elements of a uniform pseudorandom sequence.

VAN_DER_CORPUT, a MATLAB library which computes elements of a van der Corput quasirandom sequence.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, September 1991, pages 345-405.
2. Franz Aurenhammer, Rolf Klein,
   Voronoi Diagrams,
   in Handbook of Computational Geometry,
   edited by J Sack, J Urrutia,
   Elsevier, 1999,
   LC: QA448.D38H36.
3. 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.
4. Qiang Du, Vance Faber, Max Gunzburger,
   Centroidal Voronoi Tessellations: Applications and Algorithms,
   SIAM Review,
   Volume 41, Number 4, December 1999, pages 637-676.
5. Michael McKay, William Conover, Richard Beckman,
   A Comparison of Three Methods for Selecting Values of Input Variables in the Analysis of Output From a Computer Code,
   Technometrics,
   Volume 21, 1979, pages 239-245.
6. Vicente Romero, John Burkardt, Max Gunzburger, Janet Peterson,
   Initial Evaluation of Pure and "Latinized" Centroidal Voronoi Tessellation for Non-Uniform Statistical Sampling,
   Sensitivity Analysis of Model Output (SAMO 2004) Conference, Santa Fe, March 8-11, 2004.
7. Yuki Saka, Max Gunzburger, John Burkardt,
   Latinized, improved LHS, and CVT point sets in hypercubes,
   submitted to IEEE Transactions on Information Theory.

Source Code:

• ch_cap.m capitalizes a single character.
• ch_eqi.m is TRUE if two characters are equal, ignoring case.
• ch_to_digit.m returns the integer value of a base 10 digit.
• cluster_energy.m returns the energy of a dataset.
• cvt.m computes a Centroidal Voronoi Tessellation.
• cvt_iteration.m takes one step of the CVT iteration.
• cvt_write.m writes a CVT dataset to a file.
• file_column_count.m counts the number of columns in the first line of a file.
• file_rows_count.m counts the number of rows in a file.
• find_closest.m finds the Voronoi cell generator closest to a point X.
• get_seed.m returns a seed for the random number generator.
• i4_to_halton.m computes an element of a vector Halton sequence.
• lcvt_write.m writes a LCVT dataset to a file.
• param_print.m prints the program parameters.
• prime.m returns any of the first PRIME_MAX prime numbers.
• r8_uniform_01.m is a portable pseudorandom number generator.
• r8mat_latinize.m "Latinizes" an R8MAT.
• r8mat_transpose_print.m prints an R8MAT, transposed, with an optional title.
• r8mat_transpose_print_some.m prints some of an R8MAT, transpose, with an optional title.
• r8vec_sort_heap_index_a.m does an indexed heap ascending sort of a real vector.
• region_sampler.m returns a sample point in the physical region.
• s_cap.m replaces any lowercase letters by uppercase ones in a string.
• s_eqi.m is TRUE if two strings are equal, ignoring case.
• s_len_trim.m returns the length of a string to the last nonblank.
• s_to_i4.m reads an I4 from a string.
• s_to_r8.m reads an R8 from a string.
• s_to_r8vec.m reads an R8VEC from a string.
• s_word_count.m returns the number of words in a string.
• test_region.m determines if a point is within the physical region.
• timestamp.m prints the current YMDHMS date as a timestamp.
• tuple_next_fast.m computes the next element of a tuple space, "fast".