CVT_MOD_DATASET
Centroidal Voronoi Tessellation on Logical Torus

CVT_MOD_DATASET is a FORTRAN90 program, using double precision arithmetic, which creates Centroidal Voronoi Tessellation (CVT) datasets in which the geometry is a logical torus.

A 2D unit logical torus is the unit square, but with "wraparound". This is the connectivity frequently seen in video games, in which a spaceship flies off the top of the screen and immediately reappears at the bottom of the screen. In the general M-dimensional case, the extreme minimum and maximum values of each coordinate are identified, and modular arithmetic may be used to determine distances.

For details on the underlying CVT calculation, refer to CVT_DATASET. This program is a modification of that one, in which distances are computed using modular arithmetic. For the current code, the region is a unit hypercube, although there's no real difficulty in allowing the widths in each dimension to vary.

A reasonable set of input commands might be:

        #  cvt_mod_02_00010.inp
        #
        m = 2
        n = 10
        seed = 123456789
        #
        initialize random
        sample_function_cvt = random
        sample_num_cvt = 500000
        iterate 100
        write cvt_mod_02_00010.txt
        #
        quit
      

Here, the user first specifies the spatial dimension M, the number of generators N, and the random number seed (for later reproducibility).

Then, the user specifies that the initial positions of the generators are to chosen at random; that during the iterations, the volume estimation will also be done using random sampling, and that the number of sampling points in an iteration will be 500,000. The iterate 100 command causes 100 iterations to be carried out, and then the resulting generators are written to a file.

Related Data and Programs:

CVT_MOD is a FORTRAN90 library which contains routines which compute the datasets. A compiled copy of this library is necessary to build CVT_MOD_DATASET.

CVT_MOD is a dataset directory which contains sample files created by CVT_MOD_DATASET.

CVT_MOD library is a FORTRAN90 library which computes CVT_MOD datasets.

TABLE is a file format which is used for the output files created by CVT_MOD_DATASET.

TABLE_DISCREPANCY is a C++ program which reads a TABLE file of points (presumed to lie in the unit hypercube) and computes bounds on the star discrepancy, a measure of dispersion.

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,
   ../../pdf/aurenhammer.pdf
2. 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
3. Qiang Du, Vance Faber, Max Gunzburger,
   Centroidal Voronoi Tessellations: Applications and Algorithms,
   SIAM Review, Volume 41, 1999, pages 637-676.
4. Lili Ju, Qiang Du, Max Gunzburger,
   Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations,
   Parallel Computing,
   Volume 28, 2002, pages 1477-1500.

Source Code:

• cvt_mod_dataset.f90, the source code;
• cvt_mod_dataset.csh, commands to compile and load the source code;

List of Routines:

• MAIN is the main program for CVT_MOD_DATASET.

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