Pacific Northwest Probability Seminar: Gravitational Allocation to Uniform Points on the Sphere

674 views · Published 20 November 2017 · 45:29 · Indexed 14 November 2026

Channel: Microsoft Research · 2017 · Science & Technology

Watch on YouTube

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.) Our main result is 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). Joint work with Nina Holden and Alex Zhai. 

See more on this video at https://www.microsoft.com/en-us/research/video/pacific-northwest-probability-seminar-gravitational-allocation-to-uniform-points-on-the-sphere/

More from this channel