English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Finding a maximum independent set (MIS) of a given fam- ily of axis-parallelrectangles is a basic problem in computational geom- etry and combinatorics.This problem has attracted significant atten- tion since the sixties, whenWegner conjectured that the corresponding duality gap, i.e., the maximumpossible ratio between the maximum independent set and the minimum hitting set(MHS), is bounded by a universal constant. An interesting special case, thatmay prove use- ful to tackling the general problem, is thediagonal-intersecting case, in which the given family of rectangles isintersected by a diagonal. Indeed, Chepoi and Felsner recently gave a factor 6approximation algorithm for MHS in this setting, and showed that the dualitygap is between 3/2 and 6. In this paper we improve upon these results. First weshow that MIS in diagonal-intersecting families is NP-complete, providing onesmallest subclass for which MIS is provably hard. Then, we derive an$O(n^2)$-time algorithm for the maximum weight independent set when, inaddition the rectangles intersect below the diagonal. This improves and extendsa classic result of Lubiw, and amounts to obtain a 2-approximation algo- rithmfor the maximum weight independent set of rectangles intersecting a diagonal.Finally, we prove that for diagonal-intersecting families the duality gap isbetween 2 and 4. The upper bound, which implies an approximation algorithm ofthe same factor, follows from a simple com- binatorial argument, while thelower bound represents the best known lower bound on the duality gap, even inthe general case.

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