Abstract
Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems.
In the first problem we want to place m unit disks, for a given constant m≥1, such that the total weight of the points from P inside the union of the disks is maximized. We present a deterministic algorithm that can compute, for any ε>0, a (1−ε)-approximation to the optimal solution in O(n logn + ε \(^{{\rm -4}{\it m}}\)log\(^{\rm 2{\it m}}\) (1/ε)) time.
In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that can compute, for any ε>0, with high probability a (1+ε)-approximation to the optimal solution in O(n (log3 n + ε − 4 log2 n )) expected time.
MdB was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301. SC was partially supported by the European Community Sixth Framework Programme under a Marie Curie Intra-European Fellowship, and by the Slovenian Research Agency, project J1-7218.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, P.K., Hagerup, T., Ray, R., Sharir, M., Smid, M., Welzl, E.: Translating a planar object to maximize point containment. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, p. 42. Springer, Heidelberg (2002)
Aronov, B., Har-Peled, S.: On approximating the depth and related problems. In: SODA 2005, pp. 886–894 (2005)
Bose, P., van Kreveld, M., Maheshwari, A., Morin, P., Morrison, J.: Translating a regular grid over a point set. Comput. Geom. Theory Appl. 25, 21–34 (2003)
Cabello, S., Díaz Báñez, J.M., Seara, C., Sellarès, J.A., Urrutia, J., Ventura, I.: Covering point sets with two disjoint disks or squares. Manuscript available at http://www.fmf.uni-lj.si/~cabello/publications/ ; Preliminary version appeared at EWCG 2005
Chazelle, B.: The Discrepancy Method: Randomness and Complexity. Cambridge University Press, New York (2001)
Chazelle, B.: The discrepancy method in computational geometry. In: Handbook of Discrete and Computational Geometry, pp. 983–996. CRC Press, Boca Raton (2004)
Chazelle, B., Lee, D.T.: On a circle placement problem. Computing 36, 1–16 (1986)
Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387–421 (1989)
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer, Berlin (2000)
Drezner, Z.: On a modified one-center model. Management Science 27, 848–851 (1991)
Drezner, Z., Wesolowsky, G.O.: Finding the circle or rectangle containing the minimum weight of points. Location Science 2, 83–90 (1994)
Gajentaan, A., Overmars, M.H.: On a class of O(n 2) problems in computational geometry. Comput. Geom. Theory Appl. 5, 165–185 (1995)
Katz, M.J., Kedem, K., Segal, M.: Improved algorithms for placing undesirable facilities. Computers and Operations Research 29, 1859–1872 (2002)
Katz, M.J., Sharir, M.: An expander-based approach to geometric optimization. SIAM J. Computing 26, 1384–1408 (1997)
Matoušek, J.: Approximations and optimal geometric divide-an-conquer. J. Comput. Syst. Sci. 50, 203–208 (1995)
Plastria, F.: Continuous covering location problems. In: Hamacher, H., Drezner, Z. (eds.) Location Analysis: Theory and Applications, ch. 2, pp. 39–83. Springer, Heidelberg (2001)
Sharir, M.: On k-sets in arrangements of curves and surfaces. Discrete Comput. Geom. 6, 593–613 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
de Berg, M., Cabello, S., Har-Peled, S. (2007). Covering Many or Few Points with Unit Disks. In: Erlebach, T., Kaklamanis, C. (eds) Approximation and Online Algorithms. WAOA 2006. Lecture Notes in Computer Science, vol 4368. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11970125_5
Download citation
DOI: https://doi.org/10.1007/11970125_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69513-4
Online ISBN: 978-3-540-69514-1
eBook Packages: Computer ScienceComputer Science (R0)