Abstract

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

Fulltext Preview

Image of the first page of the fulltext document