Covering and piercing disks with two centers

Heekap Ahn; Sangsub Kim; Christian Knauer; Lena Schlipf; Chansu Shin; Antoine E. Vigneron

doi:10.1016/j.comgeo.2012.09.002

Covering and piercing disks with two centers

Heekap Ahn, Sangsub Kim, Christian Knauer, Lena Schlipf, Chansu Shin, Antoine E. Vigneron

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	253-262
Number of pages	10
Journal	Computational Geometry: Theory and Applications
Volume	46
Issue number	3
DOIs	https://doi.org/10.1016/j.comgeo.2012.09.002
State	Published - Apr 2013

Bibliographical note

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).

ASJC Scopus subject areas

Control and Optimization
Computational Theory and Mathematics
Computational Mathematics
Geometry and Topology
Computer Science Applications

Access to Document

10.1016/j.comgeo.2012.09.002

Cite this

@article{81cc3c9dc88e4e4c81b0772c7118f738,

title = "Covering and piercing disks with two centers",

abstract = "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. {\textcopyright} 2012 Elsevier B.V.",

author = "Heekap Ahn and Sangsub Kim and Christian Knauer and Lena Schlipf and Chansu Shin and Vigneron, {Antoine E.}",

note = "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).",

year = "2013",

month = apr,

doi = "10.1016/j.comgeo.2012.09.002",

language = "English (US)",

volume = "46",

pages = "253--262",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "3",

}

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 -

Covering and piercing disks with two centers

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this