Abstract
We study a class of geometric covering and packing problems for bounded closed regions on the plane. We are given a set of axis-parallel line segments that induce a planar subdivision with bounded (rectilinear) faces. We are interested in the following problems.
- (P1) Stabbing-Subdivision::
-
Stab all closed bounded faces by selecting a minimum number of points in the plane.
- (P2) Independent-Subdivision::
-
Select a maximum size collection of pairwise non-intersecting closed bounded faces.
- (P3) Dominating-Subdivision::
-
Select a minimum size collection of bounded faces such that every other face has a non-empty intersection (i.e., sharing an edge or a vertex) with some selected face.
We show that these problems are \(\mathsf { NP }\)-hard. We even prove that these problems are \(\mathsf { NP }\)-hard when we concentrate only on the rectangular faces of the subdivision. Further, we provide constant factor approximation algorithms for the Stabbing-Subdivision problem.
S. Pandit—Partially supported by the Indo-US Science & Technology Forum (IUSSTF) under the SERB Indo-US Postdoctoral Fellowship scheme with grant number 2017/94, Department of Science and Technology, Government of India.
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
Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: FOCS, pp. 400–409 (2013)
Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discret. Comput. Geom. 48(2), 373–392 (2012)
Chuzhoy, J., Ene, A.: On approximating maximum independent set of rectangles. In: FOCS, pp. 820–829 (2016)
Czyzowicz, J., Rivera-Campo, E., Santoro, N., Urrutia, J., Zaks, J.: Guarding rectangular art galleries. Discret. Appl. Math. 50(2), 149–157 (1994)
Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12, 133–137 (1981)
Gaur, D.R., Ibaraki, T., Krishnamurti, R.: Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem. J. Algorithms 43(1), 138–152 (2002)
Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130–136 (1985)
Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discret. Math. 5(3), 422–427 (1992)
Korman, M., Poon, S.H., Roeloffzen, M.: Line segment covering of cells in arrangements. Inf. Process. Lett. 129, 25–30 (2018)
van Leeuwen, E.J.: Optimization and approximation on systems of geometric objects. Ph.D. thesis, University of Amsterdam (2009)
Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)
Mudgal, A., Pandit, S.: Covering, hitting, piercing and packing rectangles intersecting an inclined line. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, D.-Z. (eds.) COCOA 2015. LNCS, vol. 9486, pp. 126–137. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-26626-8_10
Mustafa, N.H., Raman, R., Ray, S.: Settling the APX-hardness status for geometric set cover. In: FOCS, pp. 541–550 (2014)
Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discret. Comput. Geom. 44(4), 883–895 (2010)
Pandit, S.: Dominating set of rectangles intersecting a straight line. In: Canadian Conference on Computational Geometry, CCCG, pp. 144–149 (2017)
Vazirani, V.V.: Approximation Algorithms. Springer, Hecidelberg (2001)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Jana, S., Pandit, S. (2019). Covering and Packing of Rectilinear Subdivision. In: Das, G., Mandal, P., Mukhopadhyaya, K., Nakano, Si. (eds) WALCOM: Algorithms and Computation. WALCOM 2019. Lecture Notes in Computer Science(), vol 11355. Springer, Cham. https://doi.org/10.1007/978-3-030-10564-8_30
Download citation
DOI: https://doi.org/10.1007/978-3-030-10564-8_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-10563-1
Online ISBN: 978-3-030-10564-8
eBook Packages: Computer ScienceComputer Science (R0)