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 (t_j) and radii (r_j) that cover a given set of demand points Y∈R² 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∈R²; (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 R² 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.

REFERENCES

• 1: Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998 [doi>10.1145/299917.299918]
• 2: Esther M. Arkin , Sándor P. Fekete , Joseph S. B. Mitchell, Approximation algorithms for lawn mowing and milling, Computational Geometry: Theory and Applications, v.17 n.1-2, p.25-50, Oct. 2000 [doi>10.1016/S0925-7721(00)00015-8 ]
• 3: Esther M. Arkin , Refael Hassin, Approximation algorithms for the geometric covering salesman problem, Discrete Applied Mathematics, v.55 n.3, p.197-218, Dec. 13, 1994 [doi>10.1016/0166-218X(94)90008-6 ]
• 4: Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
• 5: Chanderjit Bajaj, Proving geometric algorithm non-solvability: an application of factoring polynomials, Journal of Symbolic Computation, v.2 n.1, p.99-102, March 1986 [doi>10.1006/jsco.1997.0168 ]
• 6: Chanderjit Bajaj, The algebraic degree of geometric optimization problems, Discrete & Computational Geometry, v.3 n.2, p.177-191, Jan, 1988
• 7: V. Bilò, I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos. Geometric clustering to minimize the sum of cluster sizes. In Proc. 13th European Symp. Algorithms, Vol 3669 of LNCS, pages 460--471, 2005.
• 8: H. Brönnimann and M. T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete & Comput. Geom., 14(4):463--479, 1995.
• 9: Moses Charikar , Rina Panigrahy, Clustering to minimize the sum of cluster diameters, Journal of Computer and System Sciences, v.68 n.2, p.417-441, March 2004 [doi>10.1016/j.jcss.2003.07.0014]
• 10: A. E. F. Clementi, P. Penna, and R. Silvestri. On the power assignment problem in radio networks. Technical Report TR00-054, Electronic Colloquium on Computational Complexity, 2000.
• 11: Adrian Dumitrescu , Joseph S. B. Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, Journal of Algorithms, v.48 n.1, p.135-159, August 2003 [doi>10.1016/S0196-6774(03)00047-6]
• 12: Thomas Erlebach , Klaus Jansen , Eike Seidel, Polynomial-Time Approximation Schemes for Geometric Intersection Graphs, SIAM Journal on Computing, v.34 n.6, p.1302-1323, 2005 [doi>10.1137/S0097539702402676]
• 13: Sandor Fekete , Rolf Klein , Andreas Nuechter, Searching with an autonomous robot, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997885]
• 14: S. P. Fekete, R. Klein, and A. Nüchter. Online searching with an autonomous robot. In Algorithmic Foundations of Robotics VI, Vol 17 of Tracts in Advanced Robotics, pages 139--154. Springer, Berlin, 2005.
• 15: The GAP Group. GAP -- Groups, Algorithms, and Programming, Version 4.4, 2005.
• 16: T. F. Gonzalez. Covering a set of points in multidimensional space. Inf. Proc. Letters, 40(4):181--188, 1991.
• 17: John Hershberger, Minimizing the sum of diameters efficiently, Computational Geometry: Theory and Applications, v.2 n.2, p.111-118, Oct. 1992 [doi>10.1016/0925-7721(92)90028-Q ]
• 18: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 19: Nissan Lev-Tov , David Peleg, Polynomial time approximation schemes for base station coverage with minimum total radii, Computer Networks and ISDN Systems, v.47 n.4, p.489-501, 15 March 2005 [doi>10.1016/j.comnet.2004.08.012]
• 20: Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]
• 21: K. Pahlavan and A. H. Levesque. Wireless information networks, Vol 001. Wiley, New York, NY, 2nd ed., 2005.
• 22: J. J. Rotman. Advanced Modern Algebra. Prentice Hall, 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
approximation, complexity, covering problems, geometric optimization, tour problems