Gravitational allocation to uniform points on the sphere
Gravitational allocation to uniform points on the sphere
Given n uniform points on the surface of a two-dimensional sphere, how can we partition the sphere fairly among them ? "Fairly" means that each region has the same area. It turns out that if the given points apply a two-dimensional gravity force to the rest of the sphere, then the basins of attraction for the resulting gradient flow yield such a partition-with exactly equal areas, no matter how the points are distributed. (See the cover of the AMS Notices at http://www.ams.org/publications/journals/notices/201705/rnoti-cvr1.pdf and Dacorogna-Moser (1990) .) We show that this partition minimizes, up to a bounded factor, the average distance between points in the same cell. I will also present an application to almost optimal matching of n uniform blue points to n uniform red points on the sphere, connecting to a classical result of Ajtai, Komlos and Tusnady (Combinatorica 1984). A new impetus for this topic was given in the note "Scaling hypothesis for the Euclidean bipartite matching problem" by Caracciolo, Lucibello, Parisi and Sicuro in Physical Review E (2014) who suggested gravitational allocation as a linearization of the Monge-Ampere equation; their numerical predictions for optimal allocations and matchings were confirmed by Ambrosio, Stra and Trevisan (2016). These works suggest, but do not yet prove, that gravitational allocation yields matchings that asymptotically minimize the average squared distance between matched points. I will also describe an appealing variant, electrostatic matching, that so far has defied analysis. Joint work with Nina Holden and Alex Zhai.