Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line: Algorithms and Complexity

Abstract

Given a set of n axis-parallel rectangles in the plane, finding a maximum independent set (MIS), amaximumweighted independent set (WMIS), and aminimum hitting set (MHS), are basic problems in computational geometry and combinatorics. They have attracted significant attention since the sixties, when Wegner conjectured that the duality gap, equal to the ratio between the size of MIS and the size of MHS, is always bounded by a universal constant. An interesting case is when there exists a diagonal line that intersects each of the given rectangles. Indeed, Chepoi and Felsner recently gave a 6-approximation algorithm forMHSin this setting, and showed that the duality gap is between 3/2 and 6.We consider the same setting and improve upon these results. First, we derive an O(n2)-time algorithm for the WMIS when, in addition, every pair of intersecting rectangles have a common point below the diagonal. This improves and extends a classic result of Lubiw, and gives a 2-approximation algorithm for WMIS. Second, we show that MIS is NP-hard. Finally, we prove that the duality gap is between 2 and 4. The upper bound, which implies a 4-approximation algorithm for MHS, follows from simple combinatorial arguments, whereas the lower bound represents the best known lower bound on the duality gap, even in the general setting of the rectangles.