Abstract (EN)

We study the following geometric separation problem: Given a setRof redpoints and a setBof blue points in the plane, find a minimum-size set of lines that separateRfromB. We show that, in its full generality, parameterized by the number of lineskin the solution, the problem is unlikely to be solvable significantly faster than the brute-forcenO(k)-time algorithm, wherenis the total number of points. Indeed, we show thatan algorithm running in timef(k)no(k/logk), for any computable functionf, would disproveETH. Our reduction crucially relies on selecting lines from a set with a large number ofdifferent slopes (i.e., this number is not a function ofk).Conjecturing that the problem variant where the lines are required to be axis-parallelis FPT in the number of lines, we show the following preliminary result. SeparatingRfromBwith a minimum-size set of axis-parallel lines is FPT in the size of either set, and can besolved in timeO∗(9|B|)(assuming thatBis the smaller set).