Abstract
Given a line segment arrangement, defined as the geometric structure induced by a set of n line segments in a plane, we study the complexity of two covering problems—Cell Cover for Segments and Guarding a Set of Segments. In Cell Cover for Segments (CCS) problem, the input is a line segment arrangement and our aim is to cover all the segments with minimum number of cells. We prove that the decision version of CCS is NP-complete. Guarding a Set of Segments (GSS) Problem asks to cover all the line segments with minimum number of points in the arrangement. The decision version of GSS problem is known to be NP-complete [4]. Given k as the solution size, we prove that the GSS problem admits a kernel of \(\mathcal {O}(k^{2})\) line segments and provide an \(\mathcal {O^*}(k^{2k})\) FPT algorithm for solving GSS. We model the arrangement as its underlying planar graph which allows us to define a structural parameter called face density (d) of the arrangement, and propose an \(\mathcal {O^*}(d^{k})\) FPT algorithm for the GSS problem.
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
Bondy, A., Murty, U.: Planar Graphs, Graph Theory, Graduate Texts in Mathematics, 244, Theorem 10.28, p. 267. Springer, Berlin (2008)
Bose, P., Cardinal, J., Collette, S., Hurtado, F., Korman, M., Langerman, S., Taslakian, P.: Coloring and guarding line arrangements. Discrete Math. Theor. Comput0 Sci. 15(3), 139–154 (2013)
Brass, P.: Geometric problems on coverage in sensor networks. In: Bárány, I., Böröczky, K.J., Tóth, G.F., Pach, J. (eds.) Geometry—Intuitive, Discrete, and Convex. Bolyai Society Mathematical Studies, vol. 24, pp. 91–108. Springer, Berlin, Heidelberg (2013)
Brimkov, V.E., Leach, A., Mastroianni, M., Wu, J.: Guarding a set of line segments in the plane. Theor. Comput. Sci. 412, 1313–1324 (2011)
Brimkov, V.E., Leach, A., Wub, J., Mastroianni, M.: Approximation algorithms for a geometric set cover problem. Discrete Appl. Math. 160, 1039–1052 (2012)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. McGraw-Hill Science/Engineering/Math, 2 edn. (2001)
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms. Springer, Berlin (2015)
Das, G., Goodrich, M.T.: On the complexity of approximating and illuminating three-dimensional convex polyhedra. In: Proceeding of the 4th Workshop Algorithms Dara Structure, Lecture Notes in Computer Science. Springer, Berlin (1995)
Estivill-Castro, V., Heednacram, A., Suraweera, F.: Np-completeness and fpt results for rectilinear covering problems. J. Univers. Comput. Sci. 16(5), 622–652 (2010)
Fáry, I.: On straight line representation of planar graphs. Acta. Sci. Math. (Szeged) 11, 229–233 (1948)
Gavrilova, M.L.: Computational geometry methods and intelligent computing. In: Generalized Voronoi Diagram: A Geometry-Based Approach to Computational Intelligence. vol. 158, pp. 3–10. Springer, Berlin (2008)
Hochbaum, D., Maass, W.: Approximation schemes for covering and packing problems in image processing and vlsi. In: STACS 84: Symposium of Theoretical Aspects of Computer Science, pp. 55–62. Paris (1984)
Joshi, A., Narayanaswamy, N.S.: Approximation algorithms for hitting triangle-free sets of line segments. In: Algorithm Theory SWAT 2014. Lecture Notes in Computer Science. vol. 8503, pp. 357–367 (2014)
Das, G.K., Roy, S., Das, S., Nandy, S.C.: Variations of base station placement problem on the boundary of a convex region. Int. J. Found. Comput. Sci. 19(2), 405–427 (2008)
Korman, M., Poon, S.H., Roeloffzen, M.: Line segment covering of cells in arrangements. Inf. Process. Lett. 129, 25–30 (2018)
Lapinskaitė, I., Kuckailytė, J.: The impact of supply chain cost on the price of the final product. Bus. Manage. Educ. 12, 109–126 (2014)
Tanimoto, S.L., Fowler, R.J.: Covering image subsets with patches. In: Proceedings of the 5th International Conference on Pattern Recognition, vol. 2, pp. 835–839. MiamiBeach, Florida, USA (1980)
Whitney, H.: 2-isomorphic graphs. Amer. J. Math. pp. 245–254 (1933)
Yang, D., Misra, S., Fang, X., Xue, G., Zhang, J.: Two-tiered constrained relay node placement in wireless sensor networks: computational complexity and efficient approximations. IEEE Trans. Mob. Comput. 11(8), 1399–1411 (2012)
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 Singapore Pte Ltd.
About this paper
Cite this paper
Rema, M., Subashini, R., Methirumangalath, S., Rajan, V. (2023). Classical and Parameterized Complexity of Line Segment Covering Problems in Arrangement. In: Bhateja, V., Carroll, F., Tavares, J.M.R.S., Sengar, S.S., Peer, P. (eds) Intelligent Data Engineering and Analytics. FICTA 2023. Smart Innovation, Systems and Technologies, vol 371. Springer, Singapore. https://doi.org/10.1007/978-981-99-6706-3_29
Download citation
DOI: https://doi.org/10.1007/978-981-99-6706-3_29
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-99-6705-6
Online ISBN: 978-981-99-6706-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)