## devNotes 4-15-16 triangle grading – Voronoi cells and Delaunay triangulation

(PDF)

### Distribution of Points on a Sphere with Application to Star Catalogs

#### Covering and packing with spherical caps

A spherical cap C(x,r)C(x,r) centred at xx with radius rr is the set of all points on the sphere a distance of at most rr from the point xx. For a fixed number of points mm, the packing problem is to find the centres xjxj, j=1,,mj=1,…,m of mm 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 xjxj, j=1,,mj=1,…,m of mm 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 xjxj, j=1,,mj=1,…,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.