LCVT
Latin Centroidal Voronoi Tessellations

LCVT is a library of FORTRAN90 routines, using double precision arithmetic, for creating 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.

Related Data and Programs:

CVT is a FORTRAN90 library of routines which can compute a Centroidal Voronoi Tessellation.

FAURE is a FORTRAN90 library of routines which can compute elements of a Faure quasirandom sequence.

GRID is a FORTRAN90 library of routines which can compute elements of a grid dataset.

HALTON is a FORTRAN90 library of routines which can compute elements of a Halton quasirandom sequence.

HAMMERSLEY is a FORTRAN90 library of routines which can compute elements of a Hammersley quasirandom sequence.

HEX_GRID is a FORTRAN90 library of routines which can compute elements of a hexagonal grid dataset.

HEX_GRID_ANGLE is a FORTRAN90 library of routines which can compute elements of an angled hexagonal grid dataset.

IHS is a FORTRAN90 library of routines which can compute elements of an improved distributed Latin hypercube dataset.

LATIN_CENTER is a FORTRAN90 library of routines which can compute elements of a Latin Hypercube dataset, choosing center points.

LATIN_EDGE is a FORTRAN90 library of routines which can compute elements of a Latin Hypercube dataset, choosing edge points.

LATIN_RANDOM is a FORTRAN90 library of routines which can compute elements of a Latin Hypercube dataset, choosing points at random.

LATINIZE is an interactive FORTRAN90 program which can be used to "latinize" a dataset.

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

LCVT is a dataset directory which contains a collection of sample LCVT datasets.

LCVT_DATASET is a FORTRAN90 interactive program which allows the user to define, compute and save an LCVT dataset.

NIEDERREITER2 is a FORTRAN90 library of routines which can compute elements of a Niederreiter quasirandom sequence with base 2.

NORMAL is a FORTRAN90 library which computes elements of a sequence of pseudorandom normally distributed values.

SOBOL is a FORTRAN90 library of routines which can compute elements of a Sobol quasirandom sequence.

UNIFORM is a FORTRAN90 library of routines which can compute elements of a uniform pseudorandom sequence.

VAN_DER_CORPUT is a FORTRAN90 library of routines which can compute 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,
   ../../publications/bgpb_2002.pdf
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,
   rbgp_2004.pdf.
7. Yuki Saka, Max Gunzburger, John Burkardt,
   Latinized, improved LHS, and CVT point sets in hypercubes,
   submitted to IEEE Transactions on Information Theory,
   sgb_submitted.pdf.

Source Code:

• lcvt.f90, the source code;
• lcvt.csh, commands to compile the source code;

Examples and Tests:

• lcvt_prb.f90, a sample calling program.
• lcvt_prb.csh, commands to compile and run the sample program.
• lcvt_prb.out, the output from a run of the sample program.

List of Routines:

• CH_CAP capitalizes a single character.
• CH_EQI is a case insensitive comparison of two characters for equality.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• CLUSTER_ENERGY returns the energy of a dataset.
• CVT computes a Centroidal Voronoi Tessellation.
• CVT_ITERATION takes one step of the CVT iteration.
• CVT_WRITE writes a CVT dataset to a file.
• FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
• FILE_ROW_COUNT counts the number of row records in a file.
• FIND_CLOSEST finds the Voronoi cell generator closest to a point X.
• GET_SEED returns a seed for the random number generator.
• GET_UNIT returns a free FORTRAN unit number.
• I4_TO_HALTON computes an element of a vector Halton sequence.
• LCVT_WRITE writes a Latinized CVT dataset to a file.
• PARAM_PRINT prints the program parameters.
• PRIME returns any of the first PRIME_MAX prime numbers.
• R8_UNIFORM_01 returns a pseudorandom unit R8.
• R8MAT_LATINIZE "Latinizes" an R8MAT.
• R8MAT_TRANSPOSE_PRINT prints an R8MAT, transposed.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
• R8TABLE_DATA_READ reads data from an R8TABLE file.
• R8VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an R8VEC.
• REGION_SAMPLER returns a sample point in the physical region.
• S_BLANK_DELETE removes blanks from a string, left justifying the remainder.
• S_CAP replaces any lowercase letters by uppercase ones in a string.
• S_EQI is a case insensitive comparison of two strings for equality.
• S_TO_I4 reads an I4 from a string.
• S_TO_R8 reads an R8 from a string.
• S_TO_R8VEC reads an R8VEC from a string.
• S_WORD_COUNT counts the number of "words" in a string.
• TEST_REGION determines if a point is within the physical region.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TIMESTRING writes the current YMDHMS date into a string.
• TUPLE_NEXT_FAST computes the next element of a tuple space, "fast".

You can go up one level to the FORTRAN90 source codes.