Abstract
We study approximation algorithms for the following geometric version of the maximum coverage problem: Let \(\mathcal {P}\) be a set of n weighted points in the plane. We want to place m \(a \times b\) rectangles such that the sum of the weights of the points in \(\mathcal {P}\) covered by these rectangles is maximized. For any fixed \(\varepsilon >0\), we present efficient approximation schemes that can find a \((1-\varepsilon )\)-approximation to the optimal solution. In particular, for \(m=1\), our algorithm runs in linear time \(O(n\log (\frac{1}{\varepsilon }))\), improving over the previous result. For \(m>1\), we present an algorithm that runs in \(O(\frac{n}{\varepsilon }\log (\frac{1}{\varepsilon })+m(\frac{1}{\varepsilon })^{O(\min (\sqrt{m},\frac{1}{\varepsilon }))})\) time.
Jian Li, Bowei Zhang and Ningye Zhang’s research was supported in part by the National Basic Research Program of China Grant 2015CB358700, 2011CBA00300, 2011CBA00301, the National Natural Science Foundation of China Grant 61202009, 61033001, 61361136003. Haitao Wang’s research was supported in part by NSF under Grant CCF-1317143.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter 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. SICOMP 38(3), 899–921 (2008)
Barequet, G., Dickerson, M., Pau, P.: Translating a convex polygon to contain a maximum number of points. Computational Geometry 8(4), 167–179 (1997)
Ben-Or, M.: Lower bounds for algebraic computation trees. In: STOC, pp. 80–86. ACM (1983)
Bremner, D., Chan, T.M., Demaine, E.D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., Taslakian, P.: Necklaces, convolutions, and X + Y. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 160–171. Springer, Heidelberg (2006)
Brönnimann, H., Goodrich, M.: Almost optimal set covers in finite vc-dimension. DCG 14(1), 463–479 (1995)
Cabello, S., Díaz-Báñez, J.M., Seara, C., Sellares, J.A., Urrutia, J., Ventura, I.: Covering point sets with two disjoint disks or squares. Computational Geometry 40(3), 195–206 (2008)
Chan, T.M., Grant, E., Könemann, J., Sharpe, M.: Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In: SODA, SODA 2012, pp. 1576–1585. SIAM (2012)
Chazelle, B.M., Lee, D.-T.: On a circle placement problem. Computing 36(1–2), 1–16 (1986)
Clarkson, K.L., Varadarajan, K.: Improved approximation algorithms for geometric set cover. DCG 37(1), 43–58 (2007)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press (2009)
de Berg, M., Cabello, S., Har-Peled, S.: Covering many or few points with unit disks. Theory of Computing Systems 45(3), 446–469 (2009)
Dickerson, M., Scharstein, D.: Optimal placement of convex polygons to maximize point containment. Computational Geometry 11(1), 1–16 (1998)
Dietzfelbinger, M., Hagerup, T., Katajainen, J., Penttonen, M.: A reliable randomized algorithm for the closest-pair problem. Journal of Algorithms 25(1), 19–51 (1997)
Drezner, Z.: Noteon a modified one-center model. Management Science 27(7), 848–851 (1981)
Even, G., Rawitz, D., Shahar, S.M.: Hitting sets when the vc-dimension is small. IPL 95(2), 358–362 (2005)
Feige, U.: A threshold of ln n for approximating set cover. JACM 45(4), 634–652 (1998)
Graham, R.L.: An efficient algorith for determining the convex hull of a finite planar set. Information processing letters 1(4), 132–133 (1972)
Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and vlsi. JACM 32(1), 130–136 (1985)
Hochbaum, D.S., Pathria, A.: Analysis of the greedy approach in problems of maximum k-coverage. Naval Research Logistics 45(6), 615–627 (1998)
Imai, H., Asano, T.: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. Journal of algorithms 4(4), 310–323 (1983)
Megiddo, N., Supowit, K.J.: On the complexity of some common geometric location problems. SICOMP 13(1), 182–196 (1984)
Mustafa, N.H., Ray, S.: Ptas for geometric hitting set problems via local search. In: SCG, pp. 17–22. ACM (2009)
Nandy, S.C., Bhattacharya, B.B.: A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids. Computers & Mathematics with Applications 29(8), 45–61 (1995)
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions. Mathematical Programming 14(1), 265–294 (1978)
Tao, Y., Hu, X., Choi, D.-W., Chung, C.-W.: Approximate maxrs in spatial databases. Proceedings of the VLDB Endowment 6(13), 1546–1557 (2013)
Varadarajan, K.: Weighted geometric set cover via quasi-uniform sampling. In: STOC, pp. 641–648. ACM (2010)
Williams, R.: Faster all-pairs shortest paths via circuit complexity. In: STOC, pp. 664–673. ACM (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Li, J., Wang, H., Zhang, B., Zhang, N. (2015). Linear Time Approximation Schemes for Geometric Maximum Coverage. In: Xu, D., Du, D., Du, D. (eds) Computing and Combinatorics. COCOON 2015. Lecture Notes in Computer Science(), vol 9198. Springer, Cham. https://doi.org/10.1007/978-3-319-21398-9_44
Download citation
DOI: https://doi.org/10.1007/978-3-319-21398-9_44
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21397-2
Online ISBN: 978-3-319-21398-9
eBook Packages: Computer ScienceComputer Science (R0)