Approximability issues of guarding a set of segments
Valentin E. Brimkov · International Journal of Computer Mathematics · 2013
In this paper we consider the following problem: given a finite set of straight-line segments S in ℝ2 Finding I is a fundamental and extensively studied problem in computational geometry (see Chapter 7.2 of 24 Preparata, F. and Shamos, M. I. 1985. Computational Geometry: An Introduction, New York: Springer. [Crossref] , [Google Scholar]). Other well-known algorithms are the O((m+p) log m) Bentley and Ottmann's algorithm 2 Bentley, J. L. and Ottmann, T. A. 1979. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput., 28: 643–647. (doi:10.1109/TC.1979.1675432)[Crossref], [Web of Science ®] , [Google Scholar] and the O(p+m log2 m/log log m) Chazelle's algorithm 7 Chazelle, B. M. 1983. Reporting and counting arbitrary planar intersections Rep. CS-83-16, Department of Computer Science, Brown University, Providence, RI [Google Scholar]. , find minimum in size set V of points on the segments, such that each segment of S contains at least one point in V. We call this problem guarding a set of segments (GSS). GSS is a special case of the set cover problem where the given family of subsets can be taken as a set of intersections of the straight-line segments in S. Requiring that the given subsets can be interpreted geometrically this way is a major restriction on the input, yet it has been shown that the problem is still strongly NP-complete [V.E. Brimkov, A. Leach, M. Mastroianni, and J. Wu, Guarding a set of line segments in the plane, Theor. Comput. Sci. 412 (2011), pp. 1313–1324]. In light of this result, in Brimkov et al. [Experimental studies on approximation algorithms for guarding sets of line segments, in Advances in Visual Computing, G. Bebis, R. Boyle, B. Parvin, D. Koracin, R. Chung, R. Hammoud, M. Hussain, T. Kar-Han, R. Crawfis, D. Thalmann, D. Kao, and L. Avila, eds., ISVC 2010, Part I, Lecture Notes in Computer Science, Vol. 6453, Springer, Berlin, 2010, pp. 592–601; V.E. Brimkov, A. Leach, M. Mastroianni, and J. Wu, Approximation algorithms for a geometric set cover problem, Discrete Appl. Math. 160 (2012), pp. 1039–1052] the GSS approximability was studied both theoretically and experimentally. Here we continue these investigations. In particular, we obtain conditions under which GSS admits good approximation.