Connecting a set of circles with minimum sum of radii

Erin Wolf Chambers; Sándor P. Fekete; Hella Franziska Hoffmann; Dimitri Marinakis; Joseph S.B. Mitchell; Venkatesh Srinivasan; Ulrike Stege; Sue Whitesides

doi:10.1007/978-3-642-22300-6_16

Connecting a set of circles with minimum sum of radii

Erin Wolf Chambers
, Sándor P. Fekete
, Hella Franziska Hoffmann
, Dimitri Marinakis
, Joseph S.B. Mitchell
, Venkatesh Srinivasan
, Ulrike Stege
, Sue Whitesides

Applied Mathematics and Statistics

Saint Louis University
Technical University of Braunschweig
Kinsol Research Inc.
University of Victoria BC

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

12 Scopus citations

Abstract

We consider the problem of assigning radii to a given set of points in the plane, such that the resulting set of circles is connected, and the sum of radii is minimized. We show that the problem is polynomially solvable if a connectivity tree is given. If the connectivity tree is unknown, the problem is NP-hard if there are upper bounds on the radii and open otherwise. We give approximation guarantees for a variety of polynomial-time algorithms, describe upper and lower bounds (which are matching in some of the cases), provide polynomial-time approximation schemes, and conclude with experimental results and open problems.

Original language	English
Title of host publication	Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings
Pages	183-194
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-22300-6_16
State	Published - 2011
Event	12th International Symposium on Algorithms and Data Structures, WADS 2011 - New York, NY, United States Duration: Aug 15 2011 → Aug 17 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6844 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Symposium on Algorithms and Data Structures, WADS 2011
Country/Territory	United States
City	New York, NY
Period	08/15/11 → 08/17/11

Keywords

approximation
connectivity problems
intersection graphs
NP-hardness problems
upper and lower bounds

Access to Document

10.1007/978-3-642-22300-6_16

Cite this

Chambers, E. W., Fekete, S. P., Hoffmann, H. F., Marinakis, D., Mitchell, J. S. B., Srinivasan, V., Stege, U., & Whitesides, S. (2011). Connecting a set of circles with minimum sum of radii. In Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings (pp. 183-194). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6844 LNCS). https://doi.org/10.1007/978-3-642-22300-6_16

Chambers, Erin Wolf ; Fekete, Sándor P. ; Hoffmann, Hella Franziska et al. / Connecting a set of circles with minimum sum of radii. Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings. 2011. pp. 183-194 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{023093b9bbcb4224b3f949ab2f6328f9,

title = "Connecting a set of circles with minimum sum of radii",

abstract = "We consider the problem of assigning radii to a given set of points in the plane, such that the resulting set of circles is connected, and the sum of radii is minimized. We show that the problem is polynomially solvable if a connectivity tree is given. If the connectivity tree is unknown, the problem is NP-hard if there are upper bounds on the radii and open otherwise. We give approximation guarantees for a variety of polynomial-time algorithms, describe upper and lower bounds (which are matching in some of the cases), provide polynomial-time approximation schemes, and conclude with experimental results and open problems.",

keywords = "approximation, connectivity problems, intersection graphs, NP-hardness problems, upper and lower bounds",

author = "Chambers, \{Erin Wolf\} and Fekete, \{S{\'a}ndor P.\} and Hoffmann, \{Hella Franziska\} and Dimitri Marinakis and Mitchell, \{Joseph S.B.\} and Venkatesh Srinivasan and Ulrike Stege and Sue Whitesides",

year = "2011",

doi = "10.1007/978-3-642-22300-6\_16",

language = "English",

isbn = "9783642222993",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "183--194",

booktitle = "Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings",

note = "12th International Symposium on Algorithms and Data Structures, WADS 2011 ; Conference date: 15-08-2011 Through 17-08-2011",

}

Chambers, EW, Fekete, SP, Hoffmann, HF, Marinakis, D, Mitchell, JSB, Srinivasan, V, Stege, U & Whitesides, S 2011, Connecting a set of circles with minimum sum of radii. in Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6844 LNCS, pp. 183-194, 12th International Symposium on Algorithms and Data Structures, WADS 2011, New York, NY, United States, 08/15/11. https://doi.org/10.1007/978-3-642-22300-6_16

Connecting a set of circles with minimum sum of radii. / Chambers, Erin Wolf; Fekete, Sándor P.; Hoffmann, Hella Franziska et al.
Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings. 2011. p. 183-194 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6844 LNCS).

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

TY - GEN

T1 - Connecting a set of circles with minimum sum of radii

AU - Chambers, Erin Wolf

AU - Fekete, Sándor P.

AU - Hoffmann, Hella Franziska

AU - Marinakis, Dimitri

AU - Mitchell, Joseph S.B.

AU - Srinivasan, Venkatesh

AU - Stege, Ulrike

AU - Whitesides, Sue

PY - 2011

Y1 - 2011

N2 - We consider the problem of assigning radii to a given set of points in the plane, such that the resulting set of circles is connected, and the sum of radii is minimized. We show that the problem is polynomially solvable if a connectivity tree is given. If the connectivity tree is unknown, the problem is NP-hard if there are upper bounds on the radii and open otherwise. We give approximation guarantees for a variety of polynomial-time algorithms, describe upper and lower bounds (which are matching in some of the cases), provide polynomial-time approximation schemes, and conclude with experimental results and open problems.

AB - We consider the problem of assigning radii to a given set of points in the plane, such that the resulting set of circles is connected, and the sum of radii is minimized. We show that the problem is polynomially solvable if a connectivity tree is given. If the connectivity tree is unknown, the problem is NP-hard if there are upper bounds on the radii and open otherwise. We give approximation guarantees for a variety of polynomial-time algorithms, describe upper and lower bounds (which are matching in some of the cases), provide polynomial-time approximation schemes, and conclude with experimental results and open problems.

KW - approximation

KW - connectivity problems

KW - intersection graphs

KW - NP-hardness problems

KW - upper and lower bounds

UR - https://www.scopus.com/pages/publications/80052114614

U2 - 10.1007/978-3-642-22300-6_16

DO - 10.1007/978-3-642-22300-6_16

M3 - Conference contribution

AN - SCOPUS:80052114614

SN - 9783642222993

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 183

EP - 194

BT - Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings

T2 - 12th International Symposium on Algorithms and Data Structures, WADS 2011

Y2 - 15 August 2011 through 17 August 2011

ER -

Chambers EW, Fekete SP, Hoffmann HF, Marinakis D, Mitchell JSB, Srinivasan V et al. Connecting a set of circles with minimum sum of radii. In Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings. 2011. p. 183-194. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-22300-6_16

Connecting a set of circles with minimum sum of radii

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this