An FPT algorithm for covering cells with line segments

Saeed Mehrabi

Carleton University

Consider the set of cells induced by the arrangement of a set of $n$ line segments in the plane. We consider the problem of covering cells with the minimum number of line segments, where a line segment covers a cell if it is incident to the cell. In an earlier talk, I gave an FPT algorithm (parameterized by the size of an optimal solution) when the line segments are axis-parallel. In this talk, I will show that the problem is fixed-parameter tractable (with respect to the size of an optimal solution) when the line segments can have any orientation.