Gravitational Allocation on the Sphere
Nina Holden, Yuval Peres, Alex Zhai · 2018
Given a collection L of n points on a sphere Sn2of surface area n, a fair allocation is a partition of the sphere into n parts 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 a certain “gravitational” potential, then the expected distance between a point on the sphere and the associated point of L is O(√logn). 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 is O(√logn), which is optimal by a result of Ajtai, Komlós, and Tusnády.