Covering many or few points with unit disks. (English) Zbl 1187.68716

Summary: 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\geq 1\), such that the total weight of the points from \(P\) inside the union of the disks is maximized. We present algorithms that compute, for any fixed \(\varepsilon >0\), a \((1 - \varepsilon )\)-approximation to the optimal solution in \(O(n \log n)\) 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 computes, for any fixed \(\varepsilon >0\), in \(O(n \log ^{2} n)\) expected time a disk that is, with high probability, a \((1+\varepsilon )\)-approximation to the optimal solution.


68W25 Approximation algorithms
Full Text: DOI


[1] Agarwal, P.K., Hagerup, T., Ray, R., Sharir, M., Smid, M., Welzl, E.: Translating a planar object to maximize point containment. In: ESA 2002. LNCS, vol. 2461. Springer, Berlin (2002) · Zbl 1019.68134
[2] Agarwal, P.K., Procopiuc, C.M.: Exact and approximation algorithms for clustering. Algorithmica 33(2), 201–226 (2002) · Zbl 0994.68178
[3] Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. Wiley, New York (2000)
[4] Aronov, B., Har-Peled, S.: On approximating the depth and related problems. SIAM J. Comput. 38, 899–921 (2008) · Zbl 1180.68278
[5] 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) · Zbl 1021.65008
[6] 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. Comput. Geom. Theory Appl. 40, 195–206 (2008) · Zbl 1143.65015
[7] Chazelle, B.: The Discrepancy Method: Randomness and Complexity. Cambridge University Press, New York (2001) · Zbl 0960.65149
[8] Chazelle, B.: The discrepancy method in computational geometry. In: Handbook of Discrete and Computational Geometry, pp. 983–996. CRC, Boca Raton (2004)
[9] Chazelle, B., Lee, D.T.: On a circle placement problem. Computing 36, 1–16 (1986) · Zbl 0572.65051
[10] Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry II. Discrete Comput. Geom. 4, 387–421 (1989) · Zbl 0681.68060
[11] de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer, Berlin (2000) · Zbl 0939.68134
[12] Drezner, Z.: On a modified one-center model. Manag. Sci. 27, 848–851 (1981) · Zbl 0462.90027
[13] Drezner, Z., Wesolowsky, G.O.: Finding the circle or rectangle containing the minimum weight of points. Location Sci. 2, 83–90 (1994) · Zbl 0919.90100
[14] Gajentaan, A., Overmars, M.H.: On a class of O(n 2) problems in computational geometry. Comput. Geom. Theory Appl. 5, 165–185 (1995) · Zbl 0839.68105
[15] Halperin, D.: Arrangements. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 529–562. CRC, Boca Raton (2004)
[16] Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and vlsi. J. ACM 32(1), 130–136 (1985) · Zbl 0633.68027
[17] Katz, M.J., Kedem, K., Segal, M.: Improved algorithms for placing undesirable facilities. Comput. Oper. Res. 29, 1859–1872 (2002) · Zbl 1259.90060
[18] Katz, M.J., Sharir, M.: An expander-based approach to geometric optimization. SIAM J. Comput. 26, 1384–1408 (1997) · Zbl 0888.68116
[19] Kleinberg, J., Tardos, E.: Algorithm Design. Addison-Wesley, Reading (2005)
[20] Matoušek, J.: Efficient partition trees. Discrete Comput. Geom. 8, 315–334 (1992) · Zbl 0752.68088
[21] Matoušek, J.: Approximations and optimal geometric divide-an-conquer. J. Comput. Syst. Sci. 50, 203–208 (1995) · Zbl 0827.68048
[22] Plastria, F.: Continuous covering location problems. In: Hamacher, H., Drezner, Z. (eds.) Location Analysis: Theory and Applications, pp. 39–83. Springer, Berlin (2001), Chap. 2
[23] Sharir, M.: On k-sets in arrangements of curves and surfaces. Discrete Comput. Geom. 6, 593–613 (1991) · Zbl 0744.68132
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.