Minimum Energy
points on the sphere S²

Minimum Energy Systems

Minimum energy systems are sets of m points xj, j = 1,...,m on S2 = {x in R3 : |x| = 1} that minimize the potential energy sumi=1:m   sumj=i+1:m 1 / |  xi - xj  | where |x| denotes the Euclidean norm in R3. There are many local miminma, often with objective values close to the global minimum. A lower bound on the potential energy is (1/2)m2 + c m(3/2) where c = 3(sqrt(3)/(8pi))1/2 zeta(1/2)*L-3(1/2), zeta is the Riemann zeta function and L-3is the Dirichlet L-function with characteristic (1, -1, 0). c = -0.553051... The coefficient of the m3/2 term in the potential energy expansion can be estimated by (PE - 0.5 m2) / m3/2. The norm of the gradient with respect to a spherical parametrization of the points gives an idea how close it is to a stationary point (gradient = 0). Keep in mind the size of the objective when thinking about how small it is numerically possible to get this. The Hessian is positive definite (smallest eigenvalue > 0) so these are strict local minima.

Interpolatory Cubature

The space Pn of polynomials of degree at most n on S2 has dimension dn = (n+1)2. Cubature rule sumj = 1 to dn   wj f(xj) approximates the integral of f(x) over the surface of the unit sphere. Cubature weights w such that the cubature rule is exact for all polynomials of degree <= n satsify G w = e, e = vector of 1s. G is the reproducing kernel Gram matrix. Solving Gw = e is theoretically possible for any fundamental system (G nonsingular) but in practice depends on the condition of G, which is very poor for many (local) minima of the potential energy. Cubature rule exact for p(x) = 1 implies that the sum of cubature weights = |S2| = 4 p. Average, or equal, cubature weight is wavg = |S2| / dn Scaled cubature weights are wi / wavg , smallest   wmin / wavg <= 1, largest   wmax / wavg >= 1.

Eigenvalues and Condition numbers

Many systems have very large condition numbers, making solving a linear system for interpolation or cubature weights unreliable. 1-norm condition number is cond1(G) = || G ||1   || G-1 ||1. As Gii = dn / |S2|, trace(G) = sum of eigenvalues of G = dn2 / |S2|. lmin(G) = smallest eigenvalue. lavg(G) = average eigenvalue = dn / |S2|, lmax(G) = largest eigenvalue. 2-norm condition number is cond2(G) = lmax(G) / lmin(G) The 2-norm condition number is generally an order of magnitude less than the 1-norm condition number

Lagrangian norms

Lagranians Lj(x) = ejT G-1 g(x) for x in S2. Lebesgue constant = ||Ln|| = interpolation operator norm (as a map from C(S2) to C(S2)) is maxx in S2 ||L(x)||1. Reimer upper bound on the Lebesgue constant is R = (n+1) sqrt(lavg / lmin). Lagrangian 2-norm, maxx in S2 || Lj(x) ||2 and infinity norm, maxx in S2 maxj | Lj(x) |, are calculated by finding the global maximum over S2. The Lagrangians satisfy Lj(xj) = 1 for j = 1,...,dn and Li(xj) = 0 for i not equal to j. Thus the norms of the Lagrangians are >= 1.

Geometrical properties

The geodesic dsitance between two points x and y on the unit sphere S2 is dist(x,y) = cos-1(xT y). The spherical cap with center y and radius r is C(y, r) = {x in S2 : dist(x, y) <= r } The sphere packing problem is to place m points on a sphere to as to maximize the the minimal distance mini neq j   dist(xi, xj) between them. The minimum distance is twice the packing radius for packing spherical caps of of the same radius at each point xj, j = 1,...,m. The mesh norm is h = maxx in S2   minj=1,...,m   dist(x - xj). This is also the covering radius for covering the sphere by spherical caps of radius h centered at each of the points xj, j = 1,..., m. The Voronoi cell Vj about the point xj in S2 is Vj = {x in S2 : dist(x, xj <= dist(x, xi) for all i not equal to j The sum of the areas of all Voronoi cells is equal to the surface area |S2| Thus the average area of m Voronoi cells is Vavg = |S2| / m and the scaled areas of the Voronoi cells is |Vj| / Vavg Cui and Freeden discrepancy is D = (1 - 2 log(1 + sqrt((1 - xjT xk)/2)) ]1/2. Volume of the convex hull of a set of points on S2 is always less than the volume of the unit sphere = 4 p / 3 = 4.18879...

Caveat: All points are only approximate local minimizers of the potential energy. Attempts to find global minima have been made, with decreasing reliability as n increases.

Notes on point sets

• For each point set the text file has four items per row: the x_j, y_j, and z_j cartesian coordinates in [-1, 1], and the cubature weight w_j for that point. The number of rows is equal to the number of points.
• All points are on the unit sphere so should have x_j² + y_j² + z_j² = 1.
• The file names have three components: point set, degree, number of points.
• Background programs to search for global extrema are run. This web page and tables are updated when a better system is found.
• A gzipped tar file of the complete set of Minimum energy points is in me.tar.gz (16 Mb!).  Last updated 16-Jan-2003

References

• R. S. Womersley and I. H. Sloan, How good can polynomial interpolation on the sphere be? Advances in Computational Mathematics 23 (2001) 195--226.
• I. H. Sloan and R. S. Womersley, Extremal systems of points and numerical integration on the sphere, Applied Mathematics Report AMR15-01, University of New South Wales. extremal.pdf

Acknowlegements

• ac3, The Australian Center for Advanced Computing and Communication;
• APAC, Australian Partnership for Advanced Computing;