On the Parameterized Complexity of Red-Blue Points Separation

DOI10.4230/LIPIcs.IPEC.2017.8zbMath1443.68197arXiv1710.00637OpenAlexW2963732482MaRDI QIDQ5111867

Édouard Bonnet, Michael Lampis, Panos Giannopoulos

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

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

Related Items (1)

Monochromatic partitioning of colored points by lines

Cites Work

• Unnamed Item
• On the complexity of polyhedral separability
• On the handling of continuous-valued attributes in decision tree generation
• Separability by two lines and by nearly straight polygonal chains
• SEPARATING POINTS BY AXIS-PARALLEL LINES
• Parameterized Hardness of Art Gallery Problems
• On a minimum linear classification problem

This page was built for publication: On the Parameterized Complexity of Red-Blue Points Separation