Approximability issues of guarding a set of segments

Abstract

In this paper we consider the following problem: given a finite set of straight-line segments S in ℝ2, 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.

Keywords:

• guarding a set of segments
• set cover
• vertex cover
• NP-complete problem
• approximation algorithm

2010 AMS Subject Classifications:

• 90C27
• 68U05
• 05C35
• 05C85
• 05C62

Acknowledgements

The author thanks the three anonymous referees for their useful remarks and suggestions. Some of the issues considered in this paper have been discussed in 3.

Notes

Star graph is a tree on n vertices, as either n≤2 or there is a vertex to which all other n−1 vertices are adjacent (i.e. are leaves of the tree).

Finding I is a fundamental and extensively studied problem in computational geometry (see Chapter 7.2 of 24). Other well-known algorithms are the O((m+p) log m) Bentley and Ottmann's algorithm 2 and the O(p+m log² m/log log m) Chazelle's algorithm 7.

The procedure described in 5 finds the ordered set of edges of the graph G _S̄ , which is essentially the same.

The class of the almost tree (1) graphs had been studied earlier under the name cactus trees or cacti, see 14 15 and Figure 5, left. A cactus tree can be constructed from a tree by replacing some (or all) edges by cycles of arbitrary size.

While specifying the possible methods of random rational number generation is not among the purposes of this theoretical section, it might be worth mentioning that designing adequate random number generators is an important issue in computational statistics, computer simulation, and related disciplines. In fact, random numbers produced by a random number generator are never random; rather, they are pseudo-random. The adequacy of a random number generator is proved by passing suitable statistical tests for randomness. The most reliable generators are implemented in computer algebra systems, such as Maple, Mathematica and Matlab. Since this sophisticated matter is out of the scope of the present paper, we refer the interested reader to 18 19, the former presenting Knuth's series of statistical tests (see pp. 61–73).