Computing the Heaviest Disk and Related Problems

We present an algorithm that, given $m$ points and $n$ disks in $\mathbb{R}^2$, computes the disk that contains the maximum number of points. The algorithm runs in $O^*(m^{2/3} n^{2/3} + m^{32/59} n^{145/177} + m + n)$ expected time, where the $O^*(\cdot)$ notation hides factors of the form $n^\varepsilon$, for an arbitrarily small $\varepsilon \gt 0$, and coefficients that depend on $\varepsilon$. The algorithm is faster than existing algorithms for $m \lt n^{5/4}$, and it has similar performance bounds for $m \ge n^{5/4}$. As a matter of fact, except for disks that are fully contained in other disks, the algorithm counts the number of input points in each disk.