Gravitational allocation on the sphere

Given a collection [Formula: see text] of [Formula: see text] points on a sphere [Formula: see text] of surface area [Formula: see text] , a fair allocation is a partition of the sphere into [Formula: see text] parts each of area 1, and each is associated with a distinct point of [Formula: see text]. We show that, if the [Formula: see text] points are chosen uniformly at random and if the partition is defined by a certain “gravitational” potential, then the expected distance between a point on the sphere and the associated point of [Formula: see text] is [Formula: see text]. We use our result to define a matching between two collections of [Formula: see text] independent and uniform points on the sphere and prove that the expected distance between a pair of matched points is [Formula: see text] , which is optimal by a result of Ajtai, Komlós, and Tusnády.