Abstract. Finding a maximum independent set (MIS) of a given family of axis-parallel rectangles is a basic problem in computational geometry and combinatorics. This problem has attracted significant attention since the sixties, when Wegner conjectured that the corresponding duality gap, i.e., the maximum possible ratio between the maximum independent set and the minimum hitting set (MHS), is bounded by a universal constant. An interesting special case, that may prove useful to tackling the general problem, is the diagonal-intersecting case, in which the given family of rectangles is intersected by a diagonal. Indeed, Chepoi and Felsner recently gave a factor 6 approximation algorithm for MHS in this setting, and showed that the duality gap is between 3/2 and 6. In this paper we improve upon these results. First we show that MIS in diagonal-intersecting families is NP-complete, providing one smallest subclass for which MIS is provably hard. Then, we derive an O(n 2 )-time algorithm for the maximum weight independent set when, in addition the rectangles intersect below the diagonal. This improves and extends a classic result of Lubiw, and amounts to obtain a 2-approximation algorithm for the maximum weight independent set of rectangles intersecting a diagonal. Finally, we prove that for diagonal-intersecting families the duality gap is between 2 and 4. The upper bound, which implies an approximation algorithm of the same factor, follows from a simple combinatorial argument, while the lower bound represents the best known lower bound on the duality gap, even in the general case. An extended abstract of a preliminary version of this work appears in the proceedings of the 11th Latin American Theoretical Informatics Symposium.
Recently, Correa et al. REF showed that this problem is NP-hard even in the case of a straight line and proposed a 4-approximation algorithm for this particular case.
Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line : Algorithms and Complexity
arXiv: Computational Geometry
Mathematics Computer Science