VORONOI_WEIGHT
Estimate Voronoi Weights in a Region

VORONOI_WEIGHT is a FORTRAN90 program which estimates the volume of the Voronoi cells associated with N points contained in the M-dimensional unit hypercube.

One use for the weights produced by this calculation is for improving an equal-weight quadrature scheme. That is, we suppose that the integral of a function over the unit hypercube is to be approximated. Typically, this could be done by evaluating the function at each point in the dataset, and taking the average:

Integral(f) = sum ( 1 <= I <= N ) F(X(I) ) / N
This amounts to using a quadrature scheme in which each point has the same weight, namely 1/N.

Instead, it is possible to use the weights computed by this program, to produce a refined estimate of the integral:

Integral(f) = sum ( 1 <= I <= N ) W(I) * F(X(I) )

For more information, see the section 2.2, "Optimal Quadrature Rules", in the Du, Faber and Gunzburger reference.

The weights are the M-dimensional volumes of the Voronoi cells associated with the points. These volumes are not computed directly; instead, a sampling scheme (in fact, an equal weight quadrature method!) is used.

The program is interactive, and requires the user to:

The input commands may be stored in an file. A reasonable set of input commands might be: 


        #  halton_02_00010.inp
        #
        read halton_02_00010.txt
        sample_num = 5000
        sample_function = uniform
        estimate
        write halton_02_00010_weights.txt
        quit

Commands beginning with a "#" are comments, and are ignored by the program.

The "read halton_02_00010.txt" command causes a dataset to be read in. The format of the dataset input file allows comment lines beginning with a "#" character. Each noncomment line contains the coordinates for one point of the dataset.

The "sample_num = 5000" command specifies that the unit hypercube is to be sampled 5000 times in estimating the volumes of the Voronoi cells.

The "sample_function = uniform" command specifies that the sample points are to be generated as uniform random numbers.

The "estimate" command tells the program to carry out the estimation procedure.

The "write halton_02_00010_weight.txt" command writes the weights to a file, one weight per line. The file will contain some comment lines indicating the parameters used in constructing the weights.

The "quit" command terminates the program.

Licensing:

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

Languages:

VORONOI_WEIGHT is available in a FORTRAN90 version.

Related Data and Programs:

CVT, a FORTRAN90 library which can compute routines to estimate the coordinates of a Centroidal Voronoi Tessellation.

FAURE, a FORTRAN90 library which can compute N elements of an M-dimensional Faure sequence.

GRID, a FORTRAN90 library which can compute N elements of an M-dimensional grid sequence.

HALTON, a FORTRAN90 library which can compute N elements of an M-dimensional Halton sequence.

HAMMERSLEY, a FORTRAN90 library which can compute N elements of an M-dimensional Hammersley sequence.

IHS, a FORTRAN90 library which can compute N elements of an M-dimensional improved hypercube sample.

INTEGRAL_TEST, a FORTRAN90 program which can read the weights generated by this program, and the associated original data points, and test the corresponding quadrature rule on a number of multi-dimensional test integrals.

LATIN_CENTER, a FORTRAN90 library which can compute N elements of an M-dimensional Latin center sequence.

LATIN_EDGE, a FORTRAN90 library which can compute N elements of an M-dimensional Latin edge sequence.

LATIN_RANDOM, a FORTRAN90 library which can compute N elements of an M-dimensional Latin random sequence.

NINTLIB, a FORTRAN90 library which can estimate the integral of a function over an M-dimensional region.

QUADRATURE_RULES, a dataset directory which contains sets of files that define quadrature rules over various 1D intervals or multidimensional hypercubes.

SOBOL, a FORTRAN90 library which can compute N elements of an M-dimensional Sobol sequence.

TABLE_VORONOI, a FORTRAN90 program which can read a file containing the coordinates of a set of points in 2D, and compute information about the associated Voronoi diagram.

TEST_NINT, a FORTRAN90 library which defines test functions for multidimensional integration.

UNIFORM, a FORTRAN90 library which can compute N elements of an M-dimensional uniform random 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. Qiang Du, Vance Faber, Max Gunzburger,
    Centroidal Voronoi Tessellations: Applications and Algorithms,
    SIAM Review,
    Volume 41, Number 4, December 1999, pages 637-676.

Source Code:

Examples and Tests:

The following weight files were calculated using the input dataset cvt_02_00010.txt:

The following weight files were calculated using the input dataset cvt_02_00100.txt:

The following weight files were calculated using the input dataset cvt_02_01000.txt:

The following weight files were calculated using the input dataset cvt_02_10000.txt:

The following weight files were calculated using the input dataset cvt_07_00010.txt:

The following weight files were calculated using the input dataset cvt_07_00100.txt:

The following weight files were calculated using the input dataset cvt_07_01000.txt:

The following weight files were calculated using the input dataset cvt_16_00010.txt:

The following weight files were calculated using the input dataset cvt_16_00100.txt:

The following weight files were calculated using the input dataset cvt_16_01000.txt:

The following weight files were calculated using the input dataset halton_02_00010.txt:

The following weight files were calculated using the input dataset halton_02_00100.txt:

The following weight files were calculated using the input dataset halton_02_01000.txt:

The following weight files were calculated using the input dataset halton_02_10000.txt:

The following weight files were calculated using the input dataset halton_03_00010.txt:

The following weight files were calculated using the input dataset halton_03_00100.txt:

The following weight files were calculated using the input dataset halton_03_01000.txt:

The following weight files were calculated using the input dataset uniform_02_00010.txt:

The following weight files were calculated using the input dataset uniform_02_00100.txt:

The following weight files were calculated using the input dataset uniform_02_01000.txt:

The following weight files were calculated using the input dataset uniform_07_00010.txt:

The following weight files were calculated using the input dataset uniform_07_00100.txt:

The following weight files were calculated using the input dataset uniform_07_01000.txt:

The following weight files were calculated using the input dataset uniform_16_00010.txt:

The following weight files were calculated using the input dataset uniform_16_00100.txt:

The following weight files were calculated using the input dataset uniform_16_01000.txt:

List of Routines:

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

Last revised on 13 November 2006.