On the parameterized complexity of red-blue points separation

Abstract

We study the following geometric separation problem: Given a set $\mathcal R$ of red points and a set $\mathcal B$ of blue points in the plane, find a minimum-size set of lines that separate $\mathcal R$ from $\mathcal B$. We show that, in its full generality, parameterized by the number of lines $k$ in the solution, the problem is unlikely to be solvable significantly faster than the brute-force $n^{O(k)}$-time algorithm, where $n$ is the total number of points. Indeed, we show that an algorithm running in time $f(k)n^{o(k/ \log k)}$, for any computable function $f$, would disprove ETH. Our reduction crucially relies on selecting lines from a set with a large number of different slopes (i.e., this number is not a function of $k$).

Conjecturing that the problem variant where the lines are required to be axis-parallel is FPT in the number of lines, we show the following preliminary result. Separating $\mathcal R$ from $\mathcal B$ with a minimum-size set of axis-parallel lines is FPT in the size of either set, and can be solved in time $O^*(9^{|\mathcal B|})$ (assuming that $\mathcal B$ is the smallest set).