Processing math: 0%
An FPT al­go­rithm for cov­er­ing cells with line seg­ments
Saeed Mehrabi
Car­leton Uni­ver­sity

Con­sider the set of cells in­duced by the arrange­ment of a set of n line seg­ments in the plane. We con­sider the prob­lem of cov­er­ing cells with the min­i­mum num­ber of line seg­ments, where a line seg­ment cov­ers a cell if it is in­ci­dent to the cell. In an ear­lier talk, I gave an FPT al­go­rithm (pa­ra­me­ter­ized by the size of an op­ti­mal so­lu­tion) when the line seg­ments are axis-par­al­lel. In this talk, I will show that the prob­lem is fixed-pa­ra­me­ter tractable (with re­spect to the size of an op­ti­mal so­lu­tion) when the line seg­ments can have any ori­en­ta­tion.