GRAVITATIONAL ALLOCATION FOR UNIFORM POINTS ON THE SPHERE

Given a collection of n points on a sphere S²_n of surface area n, a fair allocation is a partition of the sphere into n cells each of area 1, and each associated with a distinct point of L. We show that if the n points are chosen uniformly at random and the partition is defined by considering a “gravitational” potential defined by the n points, then the expect√ed distance between a point on the sphere and the associated point of L (Formula presented). We use our result to define a matching between two collections of n independent and uniform points on the sphere and prove that the expected distance between a pair of matched points L is O (Formula presented), which is optimal by a result of Ajtai, Komlós and Tusnády. Furthermore, we prove that the expected number of maxima for the gravitational potential is ①(n/ log n). We also study gravitational allocation on the sphere to the zero set of a particular Gaussian polynomial, and we quantify the repulsion between the points of by proving that the expected distance between a point on the sphere and the associated point of L is O( 1 ).