CIRCLE_TEST
Circle Packing Measure.

CIRCLE_TEST is a FORTRAN90 program which analyzes point sets in the unit square (or M-dimensional unit hypercube).

The point sets are to be measured in terms of a circle-packing test. The point of the test can best be described in analogy. Suppose that, at each point in the set, we place a (two dimensional) balloon of initial radius 0. At a given instant, all the balloons begin to expand. If any two balloons touch, they instantly stop expanding. Once all the balloons have stopped expanding, we record the radius of each balloon.

The point sets we are interested in have been generated by a variety of algorithms, and are stored as datasets, of spatial dimension 2, 7 and 16, and sample sizes 10, 100, 1,000 and 10,000. The point set types include:

• Centroidal Voronoi Tessellation values,
• Faure quasirandom values,
• Halton quasirandom values,
• Hammersley quasirandom values,
• Improved Distributed Hypercube Sampling (IHS) values,
• Latin Center Square values,
• Latin Edge Square values,
• Latin Random Square values,
• Niederreiter quasirandom values (base 2),
• Sobol quasirandom values,
• uniform random values.

The amount of area covered by the circles is compared to the area of the unit square. This measurement has a certain amount of boundary effect, and is more effective when the number of points is large, so that the boundary effects can be ignored. In order to make a meaningful number to report, we prefer, then, to restrict the balloons so that they cannot extend outside the unit square. In this way we can compare the coverage for a given set of points to that produced by a maximal sphere packing set, for which the balloons are all of the same size.

Note that, for each datapoint, the radius of the associated circle is the minimum distance to the nearest boundary of the Voronoi cell containing the point.

Based on this measure of coverage, a "good" dataset would be one for which the value was maximal. We might also be interested in the variation in the sizes of the radiuses.

In the limit, the maximum relative packing density of a 2D region with equal sized spheres is 0.9069. In 3D, a density of at least 0.74 can be achieved, and it is known that no greater than 0.7796 is possible.

(in)Efficiency Note: As currently programmed, the routine is inefficient, taking execution time that is O(N^3). This is because there are about N steps of the iteration, each of which "retires" one point by finding its maximal radius; in each of the N steps, the program recomputes the distances between every unretired point and all the N points. A more clever program would construct the Voronoi diagram, and then each point would only have to worry about its nearest neighbors.

For instance, for the 2D Halton datasets, here is the table of the number of points versus unrestricted (spheres can extend out of the unit hypercube) and restricted (they can't) scores:

Points	Unrestricted	Restricted
10	0.8203	0.3884
100	0.5416	0.4067
1000	0.4299	0.3959
10000	0.4214	(unavailable)

It is a comfort to see that the restricted scores are more tightly clustered than the unrestricted ones. This is a reflection of the fact that they measure a geometrically meaningful quantity that can be compared directly to 1, the volume of the unit hypercube, and to the maximal packing density.

A collection of sample datasets, and plots of the points and the circles involved in the circle test, is available at sample_2d.

Usage:

circle_test input_file

• input_file is the input file.

Licensing:

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

Languages:

CIRCLE_TEST is available in a FORTRAN90 version.

Related Programs:

DIAPHONY, a C program which reads a file of N points in M dimensions and computes its diaphony, a measure of point dispersion.

STAR_DISCREPANCY, a C program which reads a file of N points in M dimensions, (presumed to lie in the unit hypercube) and computes bounds on the star discrepancy, a measure of dispersion, by Eric Thiemard.

TABLE_QUALITY, a FORTRAN90 program which computes the quality measures of a dataset read from a file. which can analyze a dataset that is stored in a file.

TET_MESH_QUALITY, a FORTRAN90 program which computes quality measures of a tetrahedral mesh.

TRIANGULATION_QUALITY, a FORTRAN90 program which computes quality measures of a triangulation.

Source Code:

• circle_test.f90, the source code.

Examples and Tests:

• halton_02_00010.txt, the circle test applied to 10 2D Halton points.
• halton_02_00100.txt, the circle test applied to 100 2D Halton points.
• halton_02_01000.txt, the circle test applied to 1000 2D Halton points.
• halton_02_10000.txt, the circle test applied to 10000 2D Halton points.

List of Routines:

• CIRCLE_TEST_MAIN reads a dataset, and applies the circle test.
• CIRCLE_TEST performs the circle test on a set of points.
• CH_IS_DIGIT returns .TRUE. if a character is a decimal digit.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• DIGIT_INC increments a decimal digit.
• DIGIT_TO_CH returns the character representation of a decimal digit.
• FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
• FILE_LINE_COUNT counts the number of lines in a file.
• FILE_NAME_INC generates the next filename in a series.
• GET_FILE_NAME gets the input file name.
• GET_UNIT returns a free FORTRAN unit number.
• R8_PI returns the value of pi.
• RADIUS_MAXIMUS finds the biggest possible nonintersecting sphere.
• READ_INPUT_FILE reads the data from the input file.
• SPHERE_UNIT_VOLUME_ND computes the volume of a unit sphere in ND.
• SPHERE_VOLUME_ND computes the volume of a sphere in ND.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• WORD_COUNT counts the number of "words" in a string.

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