Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Approximability of Covering Cells with Line Segments
verfasst von : Paz Carmi, Anil Maheshwari, Saeed Mehrabi, Luís Fernando Schultz, Xavier da Silveira
Erschienen in: Combinatorial Optimization and Applications
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
In COCOA 2015, Korman et al. studied the following geometric covering problem: given a set S of n line segments in the plane, find a minimum number of line segments such that every cell in the arrangement of the line segments is covered. Here, a line segment s covers a cell f if s is incident to f. The problem was shown to be \(\mathsf {NP}\)-hard, even if the line segments in S are axis-parallel, and it remains \(\mathsf {NP}\)-hard when the goal is cover the “rectangular” cells (i.e., cells that are defined by exactly four axis-parallel line segments).
In this paper, we consider the approximability of the problem. We first give a \(\mathsf {PTAS}\) for the problem when the line segments in S are in any orientation, but we can only select the covering line segments from one orientation. Then, we show that when the goal is to cover the rectangular cells using line segments from both horizontal and vertical line segments, then the problem is \(\mathsf {APX}\)-hard. We also consider the parameterized complexity of the problem and prove that the problem is \(\mathsf {FPT}\) when parameterized by the size of an optimal solution. Our \(\mathsf {FPT}\) algorithm works when the line segments in S have two orientations and the goal is to cover all cells, complementing that of Korman et al. [9] in which the goal is to cover the “rectangular” cells.