Computing the Heaviest Disk and Related Problems
We present an algorithm that, given m points and n disks in R2, computes the disk that contains the maximum number of points. The algorithm runs in O∗(m2/3n2/3 + m32/59n145/177 + m + n) expected time, where the O∗(·) notation hides factors of the form nε, for an arbitrarily small ε > 0, and coefficients that depend on ε. The algorithm is faster than existing algorithms for m < n5/4, and it has similar performance bounds for m ≥ n5/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. Our approach also gives an improved bound of O∗(m2/3n2/3 + m1/2n5/6 + m + n) on the maximum number of incidences between m points and n non-nested circles in R2 (i.e., no circle lies in the interior of another circle).
