Abstract
We study the Set Cover, Hitting Set, Piercing Set, Independent Set, Dominating Set problems, and discrete versions (Discrete Independent Set and Discrete Dominating Set) for geometric instances in the plane. We focus on certain restricted classes of geometric objects, including axis-parallel lines, strips, and rectangles. For rectangles, we consider the cases in which the rectangles are (i) anchored on a horizontal line, (ii) anchored on two lines (either two parallel lines or one vertical and one horizontal line), and (iii) stabbed by a horizontal line. Some versions of these problems have been studied previously; we focus here on the open cases, for which no complexity results were known.
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
Ahmadinejad, A., Zarrabi-Zadeh, H.: Finding maximum disjoint set of boundary rectangles with application to PCB routing. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 36(3), 412–420 (2017)
Ahmadinejad, A., Assadi, S., Emamjomeh-Zadeh, E., Yazdanbod, S., Zarrabi-Zadeh, H.: On the rectangle escape problem. Theor. Comput. Sci. 689, 126–136 (2017)
Bandyapadhyay, S., Maheshwari, A., Mehrabi, S., Suri, S.: Approximating dominating set on intersection graphs of rectangles and L-frames. Comput. Geom. 82, 32–44 (2019)
Bertossi, A.A.: Dominating sets for split and bipartite graphs. Inf. Process. Lett. 19(1), 37–40 (1984)
Chan, T.M., Grant, E.: Exact algorithms and APX-hardness results for geometric packing and covering problems. Comput. Geom. 47(2, Part A), 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)
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
Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12(3), 133–137 (1981)
Hassin, R., Megiddo, N.: Approximation algorithms for hitting objects with straight lines. Discrete Appl. Math. 30(1), 29–42 (1991)
Katz, M.J., Mitchell, J.S.B., Nir, Y.: Orthogonal segment stabbing. Comput. Geom. Theor. Appl. 30(2), 197–205 (2005)
Keil, J.M., Mitchell, J.S., Pradhan, D., Vatshelle, M.: An algorithm for the maximum weight independent set problem on outerstring graphs. Comput. Geom. Theor. Appl. 60(C), 19–25 (2017)
Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discrete Math. 5(3), 422–427 (1992)
Kong, H., Ma, Q., Yan, T., Wong, M.D.F.: An optimal algorithm for finding disjoint rectangles and its application to PCB routing. In: Design Automation Conference, pp. 212–217 (2010)
Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)
Madireddy, R.R., Mudgal, A., Pandit, S.: Hardness results and approximation schemes for discrete packing and domination problems. In: Kim, D., Uma, R.N., Zelikovsky, A. (eds.) COCOA 2018. LNCS, vol. 11346, pp. 421–435. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-04651-4_28
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
Mudgal, A., Pandit, S.: Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions. Discrete Appl. Math. 211, 143–162 (2016)
Pandit, S.: Dominating set of rectangles intersecting a straight line. In: CCCG, pp. 144–149 (2017)
Pandit, S.: Covering and packing of triangles intersecting a straight line. In: Pal, S.P., Vijayakumar, A. (eds.) CALDAM 2019. LNCS, vol. 11394, pp. 216–230. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11509-8_18
Acknowledgements
We would like to thank Joseph S. B. Mitchell for fruitful discussions in the early stages of this paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Pandit, S. (2019). On the Hardness of Some Geometric Optimization Problems with Rectangles. In: Li, Y., Cardei, M., Huang, Y. (eds) Combinatorial Optimization and Applications. COCOA 2019. Lecture Notes in Computer Science(), vol 11949. Springer, Cham. https://doi.org/10.1007/978-3-030-36412-0_34
Download citation
DOI: https://doi.org/10.1007/978-3-030-36412-0_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-36411-3
Online ISBN: 978-3-030-36412-0
eBook Packages: Computer ScienceComputer Science (R0)