Giannopoulos, P. ORCID: 0000000262611961, Bonnet, E. and Lampis, M. (2017). On the Parameterized Complexity of RedBlue Points Separation. Paper presented at the 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), 04  08 Sep 2017, Vienna, Austria.
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 minimumsize 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 bruteforce 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 axisparallel is FPT in the number of lines, we show the following preliminary result. Separating R from B with a minimumsize set of axisparallel 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 Mathematics, Computer Science & Engineering > Computer Science 
URI:  http://openaccess.city.ac.uk/id/eprint/21508 

Text
 Published Version
Available under License Creative Commons: Attribution 3.0. Download (520kB)  Preview 
Export
Downloads
Downloads per month over past year
Actions (login required)
Admin Login 