Event № 652
Abstract: Given n uniform points on the surface of a two-dimensional sphere, how can we partition the sphere fairly among them?
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 flow yield such a partition—with exactly equal areas, no matter how the points are distributed. (See 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. This has an application to almost optimal matching of n uniform blue points to n uniform red points on the sphere. I will also describe open problems regarding greedy and electrostatic matching (Joint work with Nina Holden and Alex Zhai) Another topic where local and global optimization sharply differ appears starts from the classical overhang problem: Given n blocks supported on a table, how far can they be arranged to extend beyond the edge of the table without falling off? With Paterson, Thorup, Winkler and Zwick we showed ten years ago that an overhang of order cube root of n is the best possible; a crucial element in the proof involves an optimal control problem for diffusion on a line segment and I will describe generalizations of this problem to higher dimensions (with Florescu and Racz).