In a recent IPL paper (Line segment covering of cells in arrangements. Inf. Process. Lett. 129: 25-30. 2018), Korman et al. studied the problem of covering the cells induced by the arrangement of a set of $n$ line segments in the plane with the minimum number of line segments. They proved that the problem is NP-hard and gave an FPT algorithm (parameterized by the size of an optimal cover), which works when the line segments are horizontal or vertical, and the goal is to cover only ``rectangular'' cells.

In this talk, I first give a simple PTAS for the problem when the covering line segments are selected from only one orientation. I will then show that this is tight in the sense that if the covering line segments are selected from two orientations, then the problem is APX-hard. Finally, I show how to extend the FPT algorithm of Korman et al. so as to obtain an FPT algorithm for the problem when the goal is to cover \emph{all} cells (including non-rectangular ones).​