THE MINIMUM GUARDING TREE PROBLEM

Given a set Ⅎ of non-parallel lines in the plane and a nonempty subset Ⅎ′ ⊆ Ⅎ, a guarding tree for Ⅎ′ is a tree contained in the union of the lines in Ⅎ such that if a mobile guard (agent) runs on the edges of the tree, all lines in Ⅎ′ are visited by the guard. Similarly, given a connected arrangement of line segments in the plane and a nonempty subset ′ ⊆ , we define a guarding tree for ′. The minimum guarding tree problem for a given set of lines or line segments is to find a minimum-length guarding tree for the input set. We provide a simple alternative (to [N. Xu, Complexity of minimum corridor guarding problems, Inf. Process. Lett.112(17-18) (2012) 691-696.]) proof of the problem of finding a guarding tree of minimum length for a set of orthogonal (axis-parallel) line segments in the plane. Then, we present two approximation algorithms with factors 2 and 3.98, respectively, for computing a minimum guarding tree for a subset of a set of n arbitrary non-parallel lines in the plane; their running times are O(n⁸) and O(n⁶log n), respectively. Finally, we show that this problem is NP-hard for lines in 3-space.