Abstract
In COCOA 2015, Korman et al. studied the following geometric covering problem: given a set S of n line segments in the plane, find a minimum number of line segments such that every cell in the arrangement of the line segments is covered. Here, a line segment s covers a cell f if s is incident to f. The problem was shown to be \(\mathsf {NP}\)-hard, even if the line segments in S are axis-parallel, and it remains \(\mathsf {NP}\)-hard when the goal is cover the “rectangular” cells (i.e., cells that are defined by exactly four axis-parallel line segments).
In this paper, we consider the approximability of the problem. We first give a \(\mathsf {PTAS}\) for the problem when the line segments in S are in any orientation, but we can only select the covering line segments from one orientation. Then, we show that when the goal is to cover the rectangular cells using line segments from both horizontal and vertical line segments, then the problem is \(\mathsf {APX}\)-hard. We also consider the parameterized complexity of the problem and prove that the problem is \(\mathsf {FPT}\) when parameterized by the size of an optimal solution. Our \(\mathsf {FPT}\) algorithm works when the line segments in S have two orientations and the goal is to cover all cells, complementing that of Korman et al. [9] in which the goal is to cover the “rectangular” cells.
Paz Carmi is supported by Grant 2016116 from the United States-Israel Binational Science Foundation. Anil Maheshwari is supported in part by Natural Sciences and Engineering Research Council of Canada (NSERC). Saeed Mehrabi is supported by a Carleton-Fields postdoctoral fellowship.
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
Ashok, P., Kolay, S., Misra, N., Saurabh, S.: Unique covering problems with geometric sets. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 548–558. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21398-9_43
Bandyapadhyay, S., Maheshwari, A., Mehrabi, S., Suri, S.: Approximating dominating set on intersection graphs of rectangles and L-frames. In: MFCS 2018 (2018, to appear). arXiv version https://arxiv.org/abs/1803.06216
Bose, P., et al.: Coloring and guarding arrangements. Discrete Math. Theor. Comput. Sci. 15(3), 139–154 (2013)
Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discrete Comput. Geom. 48(2), 373–392 (2012)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press, McGraw-Hill Book Company, Cambridge, New York (2001)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999). https://doi.org/10.1007/978-1-4612-0515-9
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. TCS. Springer, Heidelberg (2013). https://doi.org/10.1007/978-1-4471-5559-1
Feige, U.: A threshold of ln \(n\) for approximating set cover. J. ACM 45(4), 634–652 (1998)
Korman, M., Poon, S.-H., Roeloffzen, M.: Line segment covering of cells in arrangements. Inf. Process. Lett. 129, 25–30 (2018)
Mehrabi, S.: Approximating domination on intersection graphs of paths on a grid. In: Solis-Oba, R., Fleischer, R. (eds.) WAOA 2017. LNCS, vol. 10787, pp. 76–89. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89441-6_7
Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete Comput. Geom. 44(4), 883–895 (2010)
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425–440 (1991)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Carmi, P., Maheshwari, A., Mehrabi, S., Schultz, L.F., da Silveira, X. (2018). Approximability of Covering Cells with Line Segments. In: Kim, D., Uma, R., Zelikovsky, A. (eds) Combinatorial Optimization and Applications. COCOA 2018. Lecture Notes in Computer Science(), vol 11346. Springer, Cham. https://doi.org/10.1007/978-3-030-04651-4_29
Download citation
DOI: https://doi.org/10.1007/978-3-030-04651-4_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-04650-7
Online ISBN: 978-3-030-04651-4
eBook Packages: Computer ScienceComputer Science (R0)