Approximability of Covering Cells with Line Segments

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).