On the parameterized complexity of red-blue points separation

DOI10.4230/LIPICS.IPEC.2017.8zbMATH Open1443.68197OpenAlexW2963732482MaRDI QIDQ5111867FDOQ5111867

Authors Édouard Bonnet, Panos Giannopoulos, Michael Lampis 

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1710.00637

zbMATH Keywords

FPT algorithmW[1-hardness]geometric problemETH-based lower boundred-blue points separation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: We study the following geometric separation problem: Given a set $R$ of red points and a set $B$ of blue points in the plane, find a minimum-size set of lines that separate $R$ from $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/logk)}$, 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 $R$ from $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^{\ast }(9^{|B|})$ (assuming that $B$ is the smallest set).

Recommendations

• On the parameterized complexity of red-blue points separation
• SEPARATING POINTS BY AXIS-PARALLEL LINES
• Parameterized complexity of \textsc{Red Blue Set Cover} for lines
• Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
• On separating points by lines

Cites work

• scientific article; zbMATH DE number 6850368 (Why is no real title available?)
• On a minimum linear classification problem
• On the complexity of polyhedral separability
• On the handling of continuous-valued attributes in decision tree generation
• Parameterized hardness of art gallery problems
• SEPARATING POINTS BY AXIS-PARALLEL LINES
• Separability by two lines and by nearly straight polygonal chains

Cited in

(7)

• Separating multi-color points on a plane with fewest axis-parallel lines
• Parameterized complexity of \textsc{Red Blue Set Cover} for lines
• SEPARATING POINTS BY AXIS-PARALLEL LINES
• Monochromatic partitioning of colored points by lines
• On the parameterized complexity of red-blue points separation
• Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
• Separability of point sets by \(k\)-level linear classification trees

This page was built for publication: On the parameterized complexity of red-blue points separation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111867)