## Abstract

Given a collection of n points on a sphere S^{2}_{n} of surface area n, a fair allocation is a partition of the sphere into n cells each of area 1, and each associated with a distinct point of L. We show that if the n points are chosen uniformly at random and the partition is defined by considering a “gravitational” potential defined by the n points, then the expect√ed distance between a point on the sphere and the associated point of L (Formula presented). 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 L is O (Formula presented), which is optimal by a result of Ajtai, Komlós and Tusnády. Furthermore, we prove that the expected number of maxima for the gravitational potential is ①(n/ log n). We also study gravitational allocation on the sphere to the zero set of a particular Gaussian polynomial, and we quantify the repulsion between the points of by proving that the expected distance between a point on the sphere and the associated point of L is O( 1 ).

Original language | English (US) |
---|---|

Pages (from-to) | 287-321 |

Number of pages | 35 |

Journal | Annals of Probability |

Volume | 49 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2021 |

## Keywords

- Allocation
- bipartite matching
- gravity
- transportation

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty