Minimum-Cost Coverage of Point Sets by Disks
| dc.creator | Arkin, Esther M. | |
| dc.creator | Broennimann, Herve | |
| dc.creator | Erickson, Jeff | |
| dc.creator | Fekete, Sandor P. | |
| dc.creator | Knauer, Christian | |
| dc.creator | Lenchner, Jonathan | |
| dc.creator | Mitchell, Joseph S. B. | |
| dc.creator | Whittlesey, Kim | |
| dc.date | 2006-04-04 | |
| dc.date.accessioned | 2026-07-07T07:09:18Z | |
| dc.date.available | 2026-07-07T07:09:18Z | |
| dc.description | 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 in the plane at the smallest possible cost. We consider cost functions of the form sum_j f(r_j), where f(r)=r^alpha is the cost of transmission to radius r. Special cases arise for alpha=1 (sum of radii) and alpha=2 (total area); power consumption models in wireless network design often use an exponent alpha>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 in the plane; (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 the plane and any fixed alpha>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. | |
| dc.description | 10 pages, 4 figures, Latex, to appear in ACM Symposium on Computational Geometry 2006 | |
| dc.identifier | https://arxiv.org/abs/cs/0604008 | |
| dc.identifier | http://arxiv.org/abs/cs/0604008 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/111014 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Geometry | |
| dc.subject | F.2.2 | |
| dc.title | Minimum-Cost Coverage of Point Sets by Disks | |
| dc.type | text |