City Research Online

On the Parameterized Complexity of Red-Blue Points Separation

Giannopoulos, P. ORCID: 0000-0002-6261-1961, Bonnet, E. & Lampis, M. (2017). On the Parameterized Complexity of Red-Blue Points Separation. Paper presented at the 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), 04 - 08 Sep 2017, Vienna, Austria. doi: 10.4230/LIPIcs.IPEC.2017.8


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/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 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).

Publication Type: Conference or Workshop Item (Paper)
Additional Information: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Departments: School of Science & Technology > Computer Science
School of Science & Technology > Computer Science > giCentre
[thumbnail of main.pdf]
Text - Published Version
Available under License Creative Commons: Attribution 3.0.

Download (520kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login