Minimum-cost coverage of point sets by disks

Helmut Alt; Jeff Erickson; Jonathan Lenchner; Esther M. Arkin; Sándor P. Fekete; Joseph S.B. Mitchell; Hervé Brönnimann; Christian Knauer; Kim Whittlesey

doi:10.1145/1137856.1137922

Minimum-cost coverage of point sets by disks

Helmut Alt
, Jeff Erickson
, Jonathan Lenchner
, Esther M. Arkin
, Sándor P. Fekete
, Joseph S.B. Mitchell
, Hervé Brönnimann
, Christian Knauer
, Kim Whittlesey

Applied Mathematics and Statistics

Free University of Berlin
University of Illinois at Urbana-Champaign
IBM
Technical University of Braunschweig
Polytechnic University

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

104 Scopus citations

Abstract

We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t_j) and radii (r_j) that cover a given set of demand points Y ⊂ ℝ² at the smallest possible cost. We consider cost functions of the form Σ_jf(r_j), where f(r) = rα is the cost of transmission to radius r. Special cases arise for α = 1 (sum of radii) and α = 2 (total area); power consumption models in wireless network design often use an exponent α > 2. Different scenarios arise according to possible restrictions on the transmission centers t_j, which may be constrained to belong to a given discrete set or to lie on a line, etc. We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points t_j on a given line in order to cover demand points Y ⊂ ℝ²; (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover Y; (c) a proof of NP-hardness for a discrete set of transmission points in ℝ² and any fixed α > 1; and (d) a polynomial-time approximation scheme for the problem of computing a minimum cost covering tour (MCCT), in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a tour/path that connects the centers of the disks.

Original language	English
Title of host publication	Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
Publisher	Association for Computing Machinery (ACM)
Pages	449-458
Number of pages	10
ISBN (Print)	1595933409, 9781595933409
DOIs	https://doi.org/10.1145/1137856.1137922
State	Published - 2006
Event	22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States Duration: Jun 5 2006 → Jun 7 2006

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry
Volume	2006

Conference

Conference	22nd Annual Symposium on Computational Geometry 2006, SCG'06
Country/Territory	United States
City	Sedona, AZ
Period	06/5/06 → 06/7/06

Keywords

Approximation
Complexity
Covering problems
Geometric optimization
Tour problems

Access to Document

10.1145/1137856.1137922

Cite this

Alt, H., Erickson, J., Lenchner, J., Arkin, E. M., Fekete, S. P., Mitchell, J. S. B., Brönnimann, H., Knauer, C., & Whittlesey, K. (2006). Minimum-cost coverage of point sets by disks. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06 (pp. 449-458). (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006). Association for Computing Machinery (ACM). https://doi.org/10.1145/1137856.1137922

@inproceedings{a4e7e448329e49cbb0939373965fcd1b,

title = "Minimum-cost coverage of point sets by disks",

abstract = "We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (tj) and radii (rj) that cover a given set of demand points Y ⊂ ℝ2 at the smallest possible cost. We consider cost functions of the form Σjf(rj), where f(r) = rα is the cost of transmission to radius r. Special cases arise for α = 1 (sum of radii) and α = 2 (total area); power consumption models in wireless network design often use an exponent α > 2. Different scenarios arise according to possible restrictions on the transmission centers tj, which may be constrained to belong to a given discrete set or to lie on a line, etc. We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points tj on a given line in order to cover demand points Y ⊂ ℝ2; (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover Y; (c) a proof of NP-hardness for a discrete set of transmission points in ℝ2 and any fixed α > 1; and (d) a polynomial-time approximation scheme for the problem of computing a minimum cost covering tour (MCCT), in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a tour/path that connects the centers of the disks.",

keywords = "Approximation, Complexity, Covering problems, Geometric optimization, Tour problems",

author = "Helmut Alt and Jeff Erickson and Jonathan Lenchner and Arkin, \{Esther M.\} and Fekete, \{S{\'a}ndor P.\} and Mitchell, \{Joseph S.B.\} and Herv{\'e} Br{\"o}nnimann and Christian Knauer and Kim Whittlesey",

year = "2006",

doi = "10.1145/1137856.1137922",

language = "English",

isbn = "1595933409",

series = "Proceedings of the Annual Symposium on Computational Geometry",

publisher = "Association for Computing Machinery (ACM)",

pages = "449--458",

booktitle = "Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06",

note = "22nd Annual Symposium on Computational Geometry 2006, SCG'06 ; Conference date: 05-06-2006 Through 07-06-2006",

}

Alt, H, Erickson, J, Lenchner, J, Arkin, EM, Fekete, SP, Mitchell, JSB, Brönnimann, H, Knauer, C & Whittlesey, K 2006, Minimum-cost coverage of point sets by disks. in Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Proceedings of the Annual Symposium on Computational Geometry, vol. 2006, Association for Computing Machinery (ACM), pp. 449-458, 22nd Annual Symposium on Computational Geometry 2006, SCG'06, Sedona, AZ, United States, 06/5/06. https://doi.org/10.1145/1137856.1137922

Minimum-cost coverage of point sets by disks. / Alt, Helmut; Erickson, Jeff; Lenchner, Jonathan et al.
Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Association for Computing Machinery (ACM), 2006. p. 449-458 (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006).

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

TY - GEN

T1 - Minimum-cost coverage of point sets by disks

AU - Alt, Helmut

AU - Erickson, Jeff

AU - Lenchner, Jonathan

AU - Arkin, Esther M.

AU - Fekete, Sándor P.

AU - Mitchell, Joseph S.B.

AU - Brönnimann, Hervé

AU - Knauer, Christian

AU - Whittlesey, Kim

PY - 2006

Y1 - 2006

N2 - We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (tj) and radii (rj) that cover a given set of demand points Y ⊂ ℝ2 at the smallest possible cost. We consider cost functions of the form Σjf(rj), where f(r) = rα is the cost of transmission to radius r. Special cases arise for α = 1 (sum of radii) and α = 2 (total area); power consumption models in wireless network design often use an exponent α > 2. Different scenarios arise according to possible restrictions on the transmission centers tj, which may be constrained to belong to a given discrete set or to lie on a line, etc. We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points tj on a given line in order to cover demand points Y ⊂ ℝ2; (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover Y; (c) a proof of NP-hardness for a discrete set of transmission points in ℝ2 and any fixed α > 1; and (d) a polynomial-time approximation scheme for the problem of computing a minimum cost covering tour (MCCT), in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a tour/path that connects the centers of the disks.

AB - We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (tj) and radii (rj) that cover a given set of demand points Y ⊂ ℝ2 at the smallest possible cost. We consider cost functions of the form Σjf(rj), where f(r) = rα is the cost of transmission to radius r. Special cases arise for α = 1 (sum of radii) and α = 2 (total area); power consumption models in wireless network design often use an exponent α > 2. Different scenarios arise according to possible restrictions on the transmission centers tj, which may be constrained to belong to a given discrete set or to lie on a line, etc. We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points tj on a given line in order to cover demand points Y ⊂ ℝ2; (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover Y; (c) a proof of NP-hardness for a discrete set of transmission points in ℝ2 and any fixed α > 1; and (d) a polynomial-time approximation scheme for the problem of computing a minimum cost covering tour (MCCT), in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a tour/path that connects the centers of the disks.

KW - Approximation

KW - Complexity

KW - Covering problems

KW - Geometric optimization

KW - Tour problems

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

U2 - 10.1145/1137856.1137922

DO - 10.1145/1137856.1137922

M3 - Conference contribution

AN - SCOPUS:33748082665

SN - 1595933409

SN - 9781595933409

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 449

EP - 458

BT - Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06

PB - Association for Computing Machinery (ACM)

T2 - 22nd Annual Symposium on Computational Geometry 2006, SCG'06

Y2 - 5 June 2006 through 7 June 2006

ER -

Minimum-cost coverage of point sets by disks

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this