Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line

Correa JR; Feuilloley L.; Soto, JA

Abstract

Finding a maximum independent set 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, is bounded by a universal constant. In this paper we improve upon recent results of Chepoi and Felsner and prove that when the given family of rectangles is intersected by a diagonal, this ratio is between 2 and 4. For the upper bound we derive a simple combinatorial argument that first allows us to reprove results of Hixon, and Chepoi and Felsner and then we adapt this idea to obtain the improved bound in the diagonal intersecting case. From a computational complexity perspective, although for general rectangle families the problem is known to be NP-hard, we derive an O(n(2))-time algorithm for the maximum weight independent set when, in addition to intersecting a diagonal, the rectangles intersect below it. This improves and extends a classic result of Lubiw. As a consequence, we obtain a 2-approximation algorithm for the maximum weight independent set of rectangles intersecting a diagonal.

Más información

Título según WOS: Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line
Título de la Revista: COMPUTATIONAL LOGISTICS (ICCL 2021)
Volumen: 8392
Editorial: SPRINGER INTERNATIONAL PUBLISHING AG
Fecha de publicación: 2014
Página de inicio: 35
Página final: 46
Idioma: English
Notas: ISI