We give exact and approximation algorithms for two-center problems when the input is 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 D by two smallest congruent disks. © 2012 Elsevier B.V.
Bibliographical noteKAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Work by Ahn was supported by the National Research Foundation of Korea Grant funded by the Korean Government (MEST) (NRF-2010-0009857). Work by Schlipf was supported by the German Science Foundation (DFG) within the research training group 'Methods for Discrete Structures' (GRK 1408). Work by Shin was supported by the National Research Foundation of Korea Grant funded by the Korean Government (MEST) (NRF-2011-0002827).
ASJC Scopus subject areas
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics
- Geometry and Topology
- Computer Science Applications