Minimum-Membership Geometric Dominating Set: Complexity and Algorithms
摘要
We study the geometric version of the minimum-membership dominating set problem. In this problem, we are given a set O of geometric objects in the plane, and the goal is to find a dominating set S of O such that the maximum number of dominators in S for each object in O is the minimum. We call the maximum number of dominators in S of any object is called the depth of S. We give a polynomial-time exact algorithm for the problem when the objects are intervals on the real line. Further, the problem has polynomial-time algorithms when the objects are axis-parallel lines and axis-parallel strips. On the other hand, the discrete version of the problem is \(\textsf{NP}\) -hard, even for depth 1, for axis-parallel lines, axis-parallel strips, and axis-parallel rectangles. Finally, we show that the problem is \(\textsf{NP}\) -hard (for depth 1) when the objects are axis-parallel unit segments in the plane.