Gravitational allocation on the sphere

Nina Holden, Yuval Peres, Alex Zhai

Research output: Contribution to journalArticlepeer-review


Given a collection L of n points on a sphere S2 n of surface area n, a fair allocation is a partition of the sphere into n parts each of area 1, and each is associated with a distinct point of L. We show that, if the n 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 L is O( √ log n).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( p log n), which is optimal by a result of Ajtai, Komlós, and Tusnády.

Original languageEnglish (US)
Pages (from-to)9666-9671
Number of pages6
JournalProceedings of the National Academy of Sciences of the United States of America
Issue number39
StatePublished - Sep 25 2018


  • Allocation
  • Bipartite matching
  • Gravity
  • Transportation

ASJC Scopus subject areas

  • General

Cite this