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

Microsoft Research - Channel 9

Content provided by Microsoft Research - Channel 9. All podcast content including episodes, graphics, and podcast descriptions are uploaded and provided directly by Microsoft Research - Channel 9 or their podcast platform partner. If you believe someone is using your copyrighted work without your permission, you can follow the process outlined here https://player.fm/legal.

6+ y ago 45:28

MP4•Episode home

Archived series ("Inactive feed" status)

When? This feed was archived on January 11, 2022 07:23 (2+ y ago). Last successful fetch was on November 21, 2018 05:18 (5+ y ago)

Why? Inactive feed status. Our servers were unable to retrieve a valid podcast feed for a sustained period.

What now? You might be able to find a more up-to-date version using the search function. This series will no longer be checked for updates. If you believe this to be in error, please check if the publisher's feed link below is valid and contact support to request the feed be restored or if you have any other concerns about this.

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.

28 episodes

#Tech #Data Science #montserrat