Minimum-Cost Coverage of Point Sets by Disks
Authors:
Preprint
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 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.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Wireless Information Networks2005
- Polynomial time approximation schemes for base station coverage with minimum total radiiComputer Networks, 2005
- Clustering to minimize the sum of cluster diametersJournal of Computer and System Sciences, 2004
- Approximation algorithms for TSP with neighborhoods in the planeJournal of Algorithms, 2003
- Almost optimal set covers in finite VC-dimensionDiscrete & Computational Geometry, 1995
- Approximation algorithms for the geometric covering salesman problemDiscrete Applied Mathematics, 1994
- Minimizing the sum of diameters efficientlyComputational Geometry, 1992
- Covering a set of points in multidimensional spaceInformation Processing Letters, 1991
- The algebraic degree of geometric optimization problemsDiscrete & Computational Geometry, 1988
- Proving geometric algorithm non-solvability: An application of factoring polynomialsJournal of Symbolic Computation, 1986