Minimal dispersion on the sphere
By: Alexander E. Litvak, Mathias Sonnleitner, Tomasz Szczepanski
Potential Business Impact:
Finds biggest empty spot on a ball.
The minimal spherical cap dispersion ${\rm disp}_{\mathcal{C}}(n,d)$ is the largest number $\varepsilon\in (0,1]$ such that, no matter how $n$ points are distributed on the $d$-dimensional Euclidean unit sphere $\mathbb{S}^d$, there is always a spherical cap with normalized area $\varepsilon$ not containing any of the points. We study the behavior of ${\rm disp}_{\mathcal{C}}(n,d)$ as $n$ and $d$ grow to infinity. We develop connections to the problems of sphere covering and approximation of the Euclidean unit ball by inscribed polytopes. Existing and new results are presented in a unified way. Upper bounds on ${\rm disp}_{\mathcal{C}}(n,d)$ result from choosing the points independently and uniformly at random and possibly adding some well-separated points to close large gaps. Moreover, we study dispersion with respect to intersections of caps.
Similar Papers
A Couple of Simple Algorithms for $k$-Dispersion
Computational Geometry
Find the most spread-out points from a group.
Dispersion is (Almost) Optimal under (A)synchrony
Distributed, Parallel, and Cluster Computing
Robots find empty spots faster to spread out.
Set families: restricted distances via restricted intersections
Combinatorics
Helps find patterns in sets with specific differences.