Covering and Piercing Disks with Two Centers

Hee-Kap Ahn, Sang-Sub Kim, Christian Knauer, Lena Schlipf, Chan-Su Shin, Antoine Vigneron

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

Knowledge Graph



Sign up or login to leave a comment