GRAVITATIONAL ALLOCATION FOR UNIFORM POINTS ON THE SPHERE

• 成果类型: Article
• 署名作者: Holden, Nina; Peres, Yuval; Zhai, Alex
• 署名单位: Massachusetts Institute of Technology (MIT); Microsoft; Stanford University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/20-AOP1452
• 发表日期: 2021
• 页码: 287-321
• 关键词: average-case analysis; stable marriage; Poisson; transportation; CONVERGENCE; bounds; head

摘要

Given a collection L of n points on a sphere S-n(2) 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 expected distance between a point on the sphere and the associated point of L is O (root log n) which is optimal by a result of Ajtai, Komlos and Tusnady. Furthermore, we prove that the expected number of maxima for the gravitational potential is Theta(n/log n). We also study gravitational allocation on the sphere to the zero set L of a particular Gaussian polynomial, and we quantify the repulsion between the points of L by proving that the expected distance between a point on the sphere and the associated point of L is O(1).