Spherical Centroidal Voronoi Tesselation

SPHERE_CVT is a FORTRAN90 program which seeks to determine N well-separated sites on the unit sphere in 3D, using centroidal Voronoi tessellation (CVT) techniques.

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 at random on the sphere, and then applies probabilistic centroidal Voronoi tessellation techniques in an attempt to force the the CVT condition to be satisfied. The output of the program is an XYZ file containing the coordinates of the points.

According to Steven Fortune, it is possible to compute the Delaunay triangulation of points on a sphere by computing their convex hull. If the sphere is the unit sphere at the origin, the facet normals are the Voronoi vertices.


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


SPHERE_CVT is available in a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

SPHERE_DELAUNAY, a FORTRAN90 program which computes the Delaunay triangulation of points on a sphere.

SPHERE_DESIGN_RULE, 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_INTEGRALS, a FORTRAN90 library which defines test functions for integration over the surface of the unit sphere in 3D.

SPHERE_LEBEDEV_RULE, a dataset directory which contains sets of points on a sphere which can be used for quadrature rules of a known precision;

SPHERE_QUAD, a FORTRAN90 library which estimates the integral of a function defined on the sphere.

SPHERE_STEREOGRAPH, a FORTRAN90 library which computes the stereographic mapping between points on the unit sphere and points on the plane Z = 1; a generalized mapping is also available.

SPHERE_VORONOI, a FORTRAN90 program which computes and plots the Voronoi diagram of points on the unit sphere.

SPHERE_VORONOI_DISPLAY_OPENGL, 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.

SPHERE_XYZ_DISPLAY, a MATLAB program which reads XYZ information defining points in 3D, and displays a unit sphere and the points in the MATLAB graphics window.

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


  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. Jacob Goodman, Joseph ORourke, editors,
    Handbook of Discrete and Computational Geometry,
    Second Edition,
    CRC/Chapman and Hall, 2004,
    ISBN: 1-58488-301-4,
    LC: QA167.H36.
  4. 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.
  5. Edward Saff, Arno Kuijlaars,
    Distributing Many Points on a Sphere,
    The Mathematical Intelligencer,
    Volume 19, Number 1, 1997, pages 5-11.

Source Code:

Examples and Tests:

SPIRAL32 carries out a calculation that begins with 32 points on a spiral.

List of Routines:

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

Last revised on 26 August 2010.