  Finding a maximum independent set (MIS) of a given fam- ily of axis-parallel
rectangles is a basic problem in computational geom- etry and combinatorics.
This problem has attracted significant atten- tion 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 use- ful 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 algo- rithm
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 com- binatorial argument, while the
lower bound represents the best known lower bound on the duality gap, even in
the general case.
