# 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:

• specify the file containing the point set:
• specify the sampling method:
sample_function = RANDOM / UNIFORM / HALTON / GRID
generate sample points using RANDOM_NUMBER, or UNIFORM, or HALTON, or GRID;
• specify the number of sampling points:
sample_num = 200000
• request that the weights be estimated:
estimate
• request that the weights be written to a file:
write halton_02_00010_weights.txt
• Quit
quit

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

```
#  halton_02_00010.inp
#
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.

### 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:

• MAIN is the main program for VORONOI_WEIGHT.
• 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.
• DATA_READ reads generator coordinate data from 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_VECTOR computes an element of a vector Halton sequence.
• PRIME returns any of the first PRIME_MAX prime numbers.
• R8_UNIFORM_01 returns a unit pseudorandom R8.
• 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.
• 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".
• VORONOI_WEIGHT_ESTIMATE estimates the volumes of Voronoi regions.
• VORONOI_WEIGHT_WRITE writes a Voronoi weight dataset to a file.

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

Last revised on 13 November 2006.