Abstract
We consider special cases of
,
,
, and
problems for axis-parallel squares and axis-parallel rectangles in the plane, where the objects are intersecting an
, or equivalently a
. We prove that for axis-parallel unit squares the hitting set and set cover problems are \({\mathsf {NP}}\)-complete, whereas the piercing set and independent set problems are in \({\mathsf {P}}\). For axis-parallel rectangles, we prove that the piercing set problem is \({\mathsf {NP}}\)-complete, which solves an open question from Correa et al. [Discrete & Computational Geometry (2015) [3]]. Further, we give a \({n^{O({\lceil }\log c{\rceil }+1)}}\) time exact algorithm for the independent set problem with axis-parallel squares, where n is the number of squares and side lengths of the squares vary from 1 to c. We also prove that when the given objects are unit-height rectangles, both the hitting set and set cover problems are \({\mathsf {NP}}\)-complete. For the same set of objects, we prove that the independent set problem can be solved in polynomial time.
Partially supported by grant No. SB/FTP/ETA-434/2012 under DST-SERB Fast Track Scheme for Young Scientist.
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
Chan, T.M., Grant, E.: Exact algorithms and APX-hardness results for geometric packing and covering problems. Comput. Geom. Part A 47(2), 112–124 (2014)
Chepoi, V., Felsner, S.: Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve. Comput. Geom. 46(9), 1036–1041 (2013)
Correa, J., Feuilloley, L., Pérez-Lantero, P., Soto, J.A.: Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity. Discrete Comput. Geom. 53(2), 344–365 (2015)
Das, G.K., De, M., Kolay, S., Nandy, S.C., Sur-Kolay, S.: Approximation algorithms for maximum independent set of a unit disk graph. Inf. Process. Lett. 115(3), 439–446 (2015)
Erlebach, T., Jan Van Leeuwen, E.: PTAS for weighted set cover on unit squares. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010. LNCS, vol. 6302. Springer, Heidelberg (2010)
Fraser, R., Lopez-Ortiz, A.: The within-strip discrete unit disk cover problem. In: CCCG 2012, pp. 53–58, Charlottetown, Canada, August 8–10, 2012 (2012)
Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826–834 (1977)
Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discrete Math. 5(3), 422–427 (1992)
Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)
Lubiw, A.: A weighted min-max relation for intervals. J. Combinatorial Theor. Ser. B 53(2), 151–172 (1991)
Acknowledgements
The second author would like to thank Subhas C. Nandy and Aniket Basu Roy for helpful discussions. We express our gratitude to the anonymous reviewers for reviewing our manuscript.
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
Mudgal, A., Pandit, S. (2015). Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, DZ. (eds) Combinatorial Optimization and Applications. Lecture Notes in Computer Science(), vol 9486. Springer, Cham. https://doi.org/10.1007/978-3-319-26626-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-26626-8_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26625-1
Online ISBN: 978-3-319-26626-8
eBook Packages: Computer ScienceComputer Science (R0)