Giannopoulos, P. ORCID: 0000000262611961, Bonnet, E. and Lampis, M. (2019). On the Parameterized Complexity of RedBlue Points Separation. Journal of Computational Geometry, 10(1), pp. 181206. doi: 10.20382/jocg.v10i1a7
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 nO(k) time algorithm, where n is the total number of points. Indeed, we show that an algorithm running in time f(k)nᵒ(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∗(9B) (assuming that B is the smaller set).

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