Anzeige
Erschienen in:
2021 | OriginalPaper | Buchkapitel
On the Geometric Red-Blue Set Cover Problem
verfasst von : Raghunath Reddy Madireddy, Subhas C. Nandy, Supantha Pandit
Erschienen in: WALCOM: Algorithms and Computation
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We study the variations of the geometric Red-Blue Set Cover (RBSC) problem in the plane using various geometric objects. We show that the RBSC problem with intervals on the real line is polynomial-time solvable. The problem is \(\mathsf {NP}\)-hard for rectangles anchored on two parallel lines and rectangles intersecting a horizontal line. The problem admits a polynomial-time algorithm for axis-parallel lines. However, if the objects are horizontal lines and vertical segments, the problem becomes \(\mathsf {NP}\)-hard. Further, the problem is \(\mathsf {NP}\)-hard for axis-parallel unit segments.
We introduce a variation of the Red-Blue Set Cover problem with the set system, the Special-Red-Blue Set Cover problem, and show that the problem is \(\mathsf {APX}\)-hard. We then show that several geometric variations of the problem with: (i) axis-parallel rectangles containing the origin in the plane, (ii) axis-parallel strips, (iii) axis-parallel rectangles that are intersecting exactly zero or four times, (iv) axis-parallel line segments, and (v) downward shadows of line segments, are \(\mathsf {APX}\)-hard by providing encodings of these problems as the Special-Red-Blue Set Cover problem. This is on the same line of the work by Chan and Grant [6], who provided the \(\mathsf {APX}\)-hardness results of the geometric set cover problem for the above classes of objects.