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

Siebel School of Computing and Data Science

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

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 (US)
Title of host publication	Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
Publisher	Association for Computing Machinery
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

Other

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

Keywords

Approximation
Complexity
Covering problems
Geometric optimization
Tour problems

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Online availability

10.1145/1137856.1137922

Library availability

Discover UIUC Full Text

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. 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, 2006. p. 449-458 (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006).

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

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, pp. 449-458, 22nd Annual Symposium on Computational Geometry 2006, SCG'06, Sedona, AZ, United States, 6/5/06. https://doi.org/10.1145/1137856.1137922

@inproceedings{a0a24066a9514403a8181672c97609ab,

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 (US)",

isbn = "1595933409",

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

publisher = "Association for Computing Machinery",

pages = "449--458",

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

address = "United States",

}

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 - http://www.scopus.com/inward/record.url?scp=33748082665&partnerID=8YFLogxK

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

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

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

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this