SCVT
Spherical Centroidal Voronoi Tesselation

SCVT is a FORTRAN90 program which places N well-separated points on the unit sphere in 3D.

The code assumes that good separation will follow automatically if the points are the centroids of their Voronoi regions. Thus, the code actually places N points are random on the sphere, and then applies probababilistic centroidal Voronoi tesselation techniques in an attempt to force the the CVT condition to be true. The output of the program is an XYZ file containing the coordinates of the points.

Licensing:

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

Related Data and Programs:

SPHERE_DESIGN_RULE is a FORTRAN90 library which returns point sets on the surface of the unit sphere, known as "designs", which can be useful for estimating integrals on the surface, among other uses.

SPHERE_VORONOI_DISPLAY_OPEN_GL, a C++ program which displays a sphere and randomly selected generator points, and then gradually colors in points in the sphere that are closest to each generator.

STRI_QUAD is a FORTRAN90 library which estimates the integral of a function defined on the sphere.

STRIPACK is a FORTRAN90 library which can determine the Voronoi diagram or Delaunay triangulation of a given set of points on the sphere.

SXYZ_VORONOI is a FORTRAN90 library which computes and plots Delaunay triangulations and Voronoi diagrams of points on the sphere.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, pages 345-405, September 1991.
2. Qiang Du, Vance Faber, Max Gunzburger,
   Centroidal Voronoi Tesselations: Applications and Algorithms,
   SIAM Review, Volume 41, 1999, pages 637-676.
3. Douglas Hardin, Edward Saff,
   Discretizing Manifolds via Minimum Energy Points,
   Notices of the American Mathematical Society,
   Volume 51, Number 10, November 2004, pages 1186-1194.
4. Edward Saff, Arno Kuijlaars,
   Distributing Many Points on a Sphere,
   The Mathematical Intelligencer,
   Volume 19, Number 1, 1997, pages 5-11.

Source Code:

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

Examples and Tests:

• 32 random points.
• Delaunay refinement, start with soccer ball centers, add midpoints of Delaunay sides;
• Voronoi refinement, start with soccer ball centers, add Voronoi vertices;
• 32 soccer ball centers.
• 32 spiral point centers.

List of Routines:

• MAIN is the main program for SCVT.
• DELAUNAY_MIDPOINTS returns the midpoints of a Delaunay triangulation.
• FIND_CLOSEST finds the nearest R point to each S point.
• GENERATOR_INITIALIZE sets initial values for the generators.
• HALTON_MEMORY sets or returns quantities associated with the Halton sequence.
• HALTON_VECTOR_SEQUENCE computes the next N elements in the vector Halton sequence.
• I4_MODP returns the nonnegative remainder of integer division.
• I4_TO_HALTON_VECTOR_SEQUENCE computes N elements of a vector Halton sequence.
• I4_WRAP forces an integer to lie between given limits by wrapping.
• I4VEC_INDICATOR sets an I4VEC to the indicator vector A(I)=I.
• MOTION computes the "motion" between two sets of points on the sphere.
• PRIME returns any of the first PRIME_MAX prime numbers.
• R83VEC_UNIT_L2 makes each R83 vector in an R83VEC have unit L2 norm.
• RANDOM_INITIALIZE initializes the FORTRAN 90 random number seed.
• SCVT_CENTROID computes the centroids of the regions.
• SOCCER_CENTERS returns the centers of the truncated icosahedron in 3D.
• SOCCER_VERTICES returns the vertices of the truncated icosahedron in 3D.
• SPHERE_UNIT_HALTONS_3D picks a Halton point on the unit sphere in 3D.
• SPHERE_UNIT_SAMPLES_3D picks a random point on the unit sphere in 3D.
• SPHERE_UNIT_SPIRALPOINTS_3D produces spiral points on the unit sphere in 3D.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TIMESTRING writes the current YMDHMS date into a string.
• VORONOI_VERTICES returns the vertices of a Voronoi diagram.
• XYZ_PRINT prints out a set of XYZ points.
• XYZ_WRITE writes out a set of XYZ points to a file.

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