TY - JOUR
T1 - Covering and piercing disks with two centers
AU - Ahn, Heekap
AU - Kim, Sangsub
AU - Knauer, Christian
AU - Schlipf, Lena
AU - Shin, Chansu
AU - Vigneron, Antoine E.
N1 - KAUST 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).
PY - 2013/4
Y1 - 2013/4
N2 - 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.
AB - 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.
UR - http://hdl.handle.net/10754/562693
UR - http://arxiv.org/abs/arXiv:1201.1198v1
UR - http://www.scopus.com/inward/record.url?scp=84869088590&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2012.09.002
DO - 10.1016/j.comgeo.2012.09.002
M3 - Article
SN - 0925-7721
VL - 46
SP - 253
EP - 262
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 3
ER -