Covering and Piercing Disks with Two Centers

摘要

We consider new versions of the two-center problem where the input consists of a set D of disks in the plane. We first study the problem of finding two smallest congruent disks such that each disk in D intersects one of these two disks. Then we study the problem of covering the set V by two smallest congruent disks. We give exact and approximation algorithms for these versions.