Abstract
Given a set P of points and a set U of axis-parallel unit squares in the Euclidean plane, a minimum ply cover of P with U is a subset of U that covers P and minimizes the number of squares that share a common intersection, called the minimum ply cover number of P with U. Biedl et al. [Comput. Geom., 94:101712, 2020] showed that determining the minimum ply cover number for a set of points by a set of axis-parallel unit squares is NP-hard, and gave a polynomial-time 2-approximation algorithm for instances in which the minimum ply cover number is constant. The question of whether there exists a polynomial-time approximation algorithm remained open when the minimum ply cover number is \(\omega (1)\). We settle this open question and present a polynomial-time \((8+\varepsilon )\)-approximation algorithm for the general problem, for every fixed \(\varepsilon >0\).
This work is supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agarwal, P.K., Ezra, E., Fox, K.: Geometric optimization revisited. In: Steffen, B., Woeginger, G.J. (eds.) Computing and Software Science - State of the Art and Perspectives, LNCS, vol. 10000, pp. 66–84. Springer, Cham (2019)
Basappa, M., Das, G.K.: Discrete unit square cover problem. Discret. Math. Algorithms Appl. 10(6), 1850072:1–1850072:18 (2018)
Biedl, T.C., Biniaz, A., Lubiw, A.: Minimum ply covering of points with disks and squares. Comput. Geom. 94, 101712 (2021)
Biniaz, A., Lin, Z.: Minimum ply covering of points with convex shapes. In: Proceedings of the 32nd Canadian Conference on Computational Geometry (CCCG), pp. 2–5 (2020)
Chan, T.M., He, Q.: Faster approximation algorithms for geometric set cover. In: Cabello, S., Chen, D.Z. (eds.) Proceedings of the 36th International Symposium on Computational Geometry (SoCG). LIPIcs, vol. 164, pp. 27:1–27:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
Demaine, E.D., Feige, U., Hajiaghayi, M., Salavatipour, M.R.: Combination can be hard: approximability of the unique coverage problem. SIAM J. Comput. 38(4), 1464–1483 (2008)
Durocher, S., Keil, J.M., Mondal, D.: Minimum ply covering of points with unit squares. CoRR abs/2208.06122 (2022)
Durocher, S., Mehrpour, S.: Interference minimization in \(k\)-connected wireless networks. In: Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG), pp. 113–119 (2017)
Erlebach, T., van Leeuwen, E.J.: Approximating geometric coverage problems. In: Teng, S. (ed.) Procedings 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1267–1276. SIAM (2008)
Erlebach, T., van Leeuwen, E.J.: PTAS for weighted set cover on unit squares. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX/RANDOM -2010. LNCS, vol. 6302, pp. 166–177. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15369-3_13
van Kreveld, M.J., Overmars, M.H.: Union-copy structures and dynamic segment trees. J. ACM 40(3), 635–652 (1993)
Kuhn, F., von Rickenbach, P., Wattenhofer, R., Welzl, E., Zollinger, A.: Interference in cellular networks: the minimum membership set cover problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 188–198. Springer, Heidelberg (2005). https://doi.org/10.1007/11533719_21
Misra, N., Moser, H., Raman, V., Saurabh, S., Sikdar, S.: The parameterized complexity of unique coverage and its variants. Algorithmica 65(3), 517–544 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Durocher, S., Keil, J.M., Mondal, D. (2023). Minimum Ply Covering of Points with Unit Squares. In: Lin, CC., Lin, B.M.T., Liotta, G. (eds) WALCOM: Algorithms and Computation. WALCOM 2023. Lecture Notes in Computer Science, vol 13973. Springer, Cham. https://doi.org/10.1007/978-3-031-27051-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-031-27051-2_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-27050-5
Online ISBN: 978-3-031-27051-2
eBook Packages: Computer ScienceComputer Science (R0)