Science Mathematics and Statistics

Distributing points on the sphere

The unit sphere \( S^2 \) in three dimensions is the set of all points \( x \) in \( R^3 \) at distance \( |x| = 1 \) from the origin. Here we are considering just the surface of the sphere, not its interior. In contrast to the circle, it is not possible to equally distribute points on the sphere except in a few special cases (the platonic solids illustrated below). Instead many different criteria are used to distribute points, including minimum energy, covering, packing, Voronoi cells, volume of their convex hull, maximum determinant, cubature weights and norms of the Lagrange polynomials. These different criteria are illustrated in the following images, all based on a set of 100 points which are at least very close to minimizing the potential energy.

Given the number of points \( m\), the basic problem is to choose their locations \( x_j \) for \( j = 1, \ldots ,m \) on the unit sphere (so for each \( j \), \( x_j \) is a 3-element vector with \( |x_j| = 1\)) to optimize (minimize or maximize) some function of the positions of the points. Most of the quantities of interest are rotationally invariant, that is a rotation of the whole set of points leaves the objective function unchanged. Thus the point sets can be normalized to have the first point at the north pole and the second point on the prime meridian. A characteristic of optimization problems on the sphere is that they have many local minima. Except in a few special cases, it is very hard to prove that a set of points is the global minimum. Many of these problems have become classical mathematical problems, many still unsolved today, which have intrigued scientists over many years, involving a wide range of mathematics from geometry to multivariate polynomials.

 

Point distributions on the unit sphere have applications ranging from global climate models for the Earth, mapping the Earth's gravitational and magnetic fields, carbon fullerenes (the buckyball or C60), crystallography, geodesic domes, spherical codes, modelling viruses, computational geometry, computer graphics, designing golf balls and even the soccer ball. Of particular interest to the UNSW Computational Mathematics Group are good point sets for (polynomial) approximation, interpolation and integration over the sphere and their geometric properties.

Convex hull, Voronoi cells and Delaunay triangulation

Given a set of points on the unit sphere one quantity of interest is the volume of the convex hull of the set of points. The convex hull is the set of all points which lie on a line segment joining two points in the set. It is also the intersection of all half spaces containing all the points. Maximum convex hull points maximize the volume of their convex hull, which lies inside the unit sphere. The dual of the maximum convex hull problem is to arrange the points so that the tangent planes to the sphere at these points encloses a polyhedron of minimum volume.

 

The geodesic distance between two points \( x \), \( y \) on the unit sphere is \( d(x, y) = \cos^{-1} (x^Ty) \), the angle between the vectors from the origin to the points \( x \) and \( y \). Here \( x^T y \) is the standard Euclidean inner product, so \( x^T x = |x|^2 \). Using this geodesic distance, a Voronoi cell \( V_j \) associated with a point \( x_j \) is the set of all points on the unit sphere which are closer to \( x_j \) than any of the other points. The Delaunay triangulation is such that no other point is contained in the circumcircle of any triangle. The Voronoi cells and the Delaunay triangulation are duals of each other. The Voronoi cells are spherical polygons. If only pentagons (5 sides), hexagons (6 sides) and heptagons (7 sides) polygons occur, then Euler's formula (that for a convex polyhedron \( V - E + F = 2 \), where \( V \) is the number of vertices, \( E \) is the number of edges and \( F \) is the number of faces, discovered by Euler around 1750) implies that there are 12 more pentagons than heptagons. In particular if there are no heptagons then there are exactly 12 pentagons with the rest hexagons, which is a close to ideal structure. The structure of the pentagons and heptagons that occur with larger numbers of points is of interest in physics as they represent sites for interactions.

Riesz s-energy

The Riesz \( s \)-energy (\( s > 0 \)) of a set of \( m \) points \( x_j \),, \( j = 1,...,m \) on the unit sphere is the sum over all pairs of distinct points of the terms \( 1/| x_i - x_j |^s \). The standard Coulomb potential used to model electrons repelling each other corresponds to \( s = 1 \). Finding point sets which minimizing the Coulomb potential is known as the Thomson problem after the work of J. J. Thomson in 1904 on "The view that the atoms of the elements consist of a number of negatively electrified corpuscles enclosed in a sphere of uniform positive electrification". The limit as \( s \) grows larger corresponds to the packing problem (see below) as the term from the closest point dominates. For \( s = 0 \) one maximizes the logarithm of the sum of the distances \( |x_i - x_j| \), which is equivalent to maximizing the product of the distances.

The minimum energy problem is to find a set of \( m \) points on the unit sphere which minimize their Riesz energy. The images above correspond to the energy when one extra point is added to the set of 100 points illustrated above for (from left to right) \( s = 0.1 \), \( s = 1 \) and \( s = 4 \).

 

Covering and packing with spherical caps

A spherical cap \( C(x, r) \) centred at \( x \) with radius \( r \) is the set of all points on the sphere a distance of at most \( r \) from the point \( x \). For a fixed number of points \( m \), the packing problem is to find the centres \(x_j \), \( j = 1, \ldots ,m \) of \( m \) identical non-overlapping spherical caps so that their common radius is maximized. This packing radius is twice the minimum angle between the points. The set of points is called a spherical code. The problem of finding a point set to maximize the minimum angle between the points is known as Tammes problem after his work on pollen grains in 1930 or the Fejes Toth problem (he proved an upper bound on the minimum distance between points in 1943). A related problem is the Kepler Conjecture (1611) that the densest packing of hard spheres in three dimensional space is hexagonal close packing with a density of around 74.048% (reportedly proved by Hales in 1998 taking some 282 pages).

On the other hand the covering problem is to find the centres \( x_j \), \( j = 1, \ldots ,m\) of \( m \) identical spherical caps which completely cover the sphere so that their common radius is minimized. This covering radius is given by the distance of the furthest point on the sphere from the closest point in the set \( x_j \), \( j = 1, \ldots ,m\) , which is also known as the mesh norm. The mesh norm can be calculated using the Voronoi cells or Delaunay triangulation. Another measure of the equidistribution of a point set is the ratio (always greater than 1) of the covering radius to the packing radius. The figure of the left gives the spherical packing for this set of points, the middle figure the distance of the point from the closest point in the set (the mesh norm is the global maximum of this function) and the figure on the right gives the spherical covering.

 

Norms of the Lagrange polynomials

Spherical polynomials, that is polynomials in three variables restricted to the surface of the sphere, of degree at most \( n \) form a space of dimension \( d_n = (n+1)^2 \). The most common basis is the spherical harmonics. A set of \( d_n \) points \( x_j \) on the sphere forms a fundamental system if a polynomial of degree at most n which is zero at the points must be zero at every point on the sphere. Given a fundamental set, the Lagrange polynomials \( \ell_j(x) \) for \( j = 1, \ldots ,d_n \) are the polynomials of degree \( n \) such that \( \ell_j(x_i) = 1 \) if \( i = j \) and 0 for all \( i \) not equal to \( j \).


The norms of the Lagrange polynomials are of fundamental interest in approximation theory. The Lebesgue constant is the maximum over the sphere of the sum of the absolute values \( | \ell_j(x)| \) of the Lagrange polynomials (the 1-norm of the vector of Lagrange polynomials). The Lagrangian sum of squares is the sum of squares of the Lagrange polynomials, while the infinity norm is the maximum of the absolute value of the Lagrange polynomials. For the 100 points these three functions are illustrated above. The aim is to choose points to minimize the global maximum over the sphere of these functions.

Interpolatory cubature, cubature weights and determinants

The integral of a function \( f(x) \) over the sphere can be approximated by the weighted (weights \( w_j \) ) sum of the values of the function values \( f(x_j) \) at the points \( x_j \) for \( j = 1, \ldots ,m \) . An interpolatory cubature rule has \( m = d_n \) points and is exact for all spherical polynomials of degree at most \( n \). For a fundamental system the weights in an interpolatory cubature rule are given by \( w_j = \) the integral over \( S^2 \) of the Lagrange polynomial \( \ell_j(x) \). As such cubature rules must be exact for the constant polynomial, the sum of the cubature weights \( w_j \) must be equal to the area \( |S^2| \) of the sphere. All the cubature weights should be positive, and as close to equal as possible. A spherical \( n \)-design is a set of \( m \) points on the unit sphere such that equal weight (\(w_j = |S^2|/m \)) cubature rule is exact for all polynomials of degree at most \( n \). These were introduced by Delsarte, Goethals and Seidel in 1977. A spherical \( n \)-design is also an example of a Quasi-Monte Carlo (QMC) rule for numerical integration over the sphere.

 

The linear system that must be solved to find the cubature weights can be so ill-conditioned that a computed solution is totally unreliable. The linear system is well conditioned if the points are chosen to maximize the determinant of a basis matrix, an idea dating back to Fekete in 1923.

The first two images above show the points on the sphere and their Delaunay triangulation coloured by their cubature weights. The last image is the negative of the log of the determinant of a basis matrix, as the point at the north pole is moved over the sphere. The walls are where this quantity becomes infinite as the basis matrix is singular.
 

Selected references

  • J. H. Conway and N. J. A. Sloane, Sphere packings: Lattices and Groups, Third Edition, (Springer-Verlag, 1998).
  • H. S. M. Coxeter, Regular Complex Polytopes, (Cambridge University Press, 1974).
  • P. Delsarte, J. M. Goethals and J. J. Seidel, Spherical codes and designs, Geometrica Dedicata 6 (1977) 263-388.
  • L. Fejes Toth, Regular Figures (Macmillan, 1964).
  • L. Fejes Toth, On the densest packing of spherical caps, American Mathematical Monthly 56 (1949) 330-331.
  • W. Freeden, T. Gervens and M. Schreiner, Constructive Approximation on the Sphere, With Applications to Geomathematics (Clarendon Press, 1998).
  • T. C. Hales, Cannonballs and Honeycombs, Notices of the American Mathematical Society 47 (2000) 440-449.
  • E. B. Saff and A. B. J. Kuijlaars, Distributing many points on the sphere, Mathematical Intelligencer 19,1 (1997) 5-11.
  • I. H. Sloan and R. S. Womersley, Extremal systems of points and numerical integration on the sphere, Advances in Computational Mathematics 21 (2004) 107-125.
  • S. Smale, Mathematical problems for the next century, Mathematical Intelligencer 20 (1998) 7-15.
  • G. G. Szpiro, Kepler's Conjecture (Wiley, 2003)
  • J. J. Thomson, On the Structure of the Atom: an Investigation of the Stability and Periods of Oscillation of a number of Corpuscles arranged at equal intervals around the Circumference of a Circle; with Application of the Results to the Theory of Atomic Structure, Philosophical Magazine Series 6, Vol 7 (1904) 237-265.
  • P. M. L. Tammes, On the origin of number and arrangement of places of exit on the surface of pollen grains, Recueil des Travaux Botanique Neerlandais 27 (1930) 1-84.
  • M. Reimer, Multivariate Polynomial Approximation (Birkhauser, 2003).
  • R. S. Womersley and I. H. Sloan, How good can polynomial interpolation on the sphere be?, Advances in Computational Mathematics 14 (2001) 195-226.

Further information

Rob Womersley, School of Mathematics and Statistics, UNSW