Intersecting Disks Using Two Congruent Disks

Abstract

We consider the Euclidean 2-center problem for a set of n disks in the plane: find two smallest congruent disks such that every disk in the set intersects at least one of the two congruent disks. We present a deterministic algorithm for the problem that returns an optimal pair of congruent disks in O(n2log3n / log log n) time. We also present a randomized algorithm with O(n2log2n / log log n) expected time. These results improve the previously best deterministic and randomized algorithms, making a step closer to the optimal algorithms for the problem. We show that the same algorithms also work for the 2-piercing problem and the restricted 2-covering problem on disks. ? 2021, Springer Nature Switzerland AG.