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.