Covering and piercing disks with two centers

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

doi:10.1007/978-3-642-25591-5_7

Covering and piercing disks with two centers

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science
Publisher	Springer Nature
Pages	50-59
Number of pages	10
ISBN (Print)	9783642255908
DOIs	https://doi.org/10.1007/978-3-642-25591-5_7
State	Published - 2011

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-25591-5_7

Cite this

@inproceedings{0626d0abf2c742fcb70ba866961ae4f0,

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

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

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",

year = "2011",

doi = "10.1007/978-3-642-25591-5_7",

language = "English (US)",

isbn = "9783642255908",

pages = "50--59",

booktitle = "Lecture Notes in Computer Science",

publisher = "Springer Nature",

}

TY - GEN

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

PY - 2011

Y1 - 2011

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

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

UR - http://hdl.handle.net/10754/564326

UR - http://link.springer.com/10.1007/978-3-642-25591-5_7

UR - http://www.scopus.com/inward/record.url?scp=84055193615&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-25591-5_7

DO - 10.1007/978-3-642-25591-5_7

M3 - Conference contribution

SN - 9783642255908

SP - 50

EP - 59

BT - Lecture Notes in Computer Science

PB - Springer Nature

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