On the parameterized complexity of red-blue points separation

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

Édouard Bonnet, Michael Lampis, Panos Giannopoulos

Publication date: 27 May 2020

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^{*}(9^{|B|})$ (assuming that $B$ is the smallest set).

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

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

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)

Cites Work

• On the complexity of polyhedral separability
• On the handling of continuous-valued attributes in decision tree generation
• SEPARATING POINTS BY AXIS-PARALLEL LINES
• Separability by two lines and by nearly straight polygonal chains
• Title not available (Why is that?)
• On a minimum linear classification problem
• Parameterized Hardness of Art Gallery Problems

Cited In (2)

• SEPARATING POINTS BY AXIS-PARALLEL LINES
• Monochromatic partitioning of colored points by lines

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)