Abstract
Given a set \({\mathcal P}\) of points in the plane, and a set \({\mathcal D}\) of unit disks of fixed location, the discrete unit disk cover problem is to find a minimum-cardinality subset \({\mathcal D}' \subseteq {\mathcal D}\) that covers all points of \({\mathcal P}\). This problem is a geometric version of the general set cover problem, where the sets are defined by a collection of unit disks. It is still NP-hard, but while the general set cover problem is not approximable within \(c \log |{\mathcal P}|\), for some constant c, the discrete unit disk cover problem was shown to admit a constant-factor approximation. Due to its many important applications, e.g., in wireless network design, much effort has been invested in trying to reduce the constant of approximation of the discrete unit disk cover problem. In this paper we significantly improve the best known constant from 72 to 38, using a novel approach. Our solution is based on a 4-approximation that we devise for the subproblem where the points of \({\mathcal P}\) are located below a line l and contained in the subset of disks of \({\mathcal D}\) centered above l. This problem is of independent interest.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Computational Geometry 14, 463–479 (1995)
Calinescu, G., Mandoiu, I.I., Wan, P.-J., Zelikovsky, A.: Selecting forwarding neighbors in wireless ad hoc networks. MONET 9(2), 101–111 (2004)
Clarkson, K.L., Varadarajan, K.: Improved approximation algorithms for geometric set cover. In: Proc. 21st ACM Sympos. Computational Geometry, pp. 135–141 (2005)
Gonzalez, T.: Covering a set of points in multidimensional space. Information Processing Letters 40, 181–188 (1991)
Hochbaum, D.S., Maas, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32, 130–136 (1985)
Johnson, D.S.: The NP-completeness column: An ongoing guide. J. Algorithms 3, 182–195 (1982)
Lev-Tov, N.: Algorithms for Geometric Optimization Problems in Wireless Networks. Ph.D. Dissertation, Weizmann Institute of Science (2005)
Narayanappa, S., Vojtechovsky, P.: An improved approximation factor for the unit disk covering problem. In: Proc. 18th Canadian Conf. Computational Geometry, pp. 15–18 (2006)
Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proc. 29th ACM Sympos. Theory of Computing, pp. 475–484 (1997)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Carmi, P., Katz, M.J., Lev-Tov, N. (2007). Covering Points by Unit Disks of Fixed Location. In: Tokuyama, T. (eds) Algorithms and Computation. ISAAC 2007. Lecture Notes in Computer Science, vol 4835. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77120-3_56
Download citation
DOI: https://doi.org/10.1007/978-3-540-77120-3_56
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77118-0
Online ISBN: 978-3-540-77120-3
eBook Packages: Computer ScienceComputer Science (R0)