City Research Online

On the Parameterized Complexity of Red-Blue Points Separation

Giannopoulos, P. ORCID: 0000-0002-6261-1961, Bonnet, E. & Lampis, M. (2019). On the Parameterized Complexity of Red-Blue Points Separation. Journal of Computational Geometry, 10(1), pp. 181-206. 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 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 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 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 smaller set).

Publication Type: Article
Subjects: G Geography. Anthropology. Recreation > GA Mathematical geography. Cartography
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology > Computer Science
School of Science & Technology > Computer Science > giCentre
SWORD Depositor:
[thumbnail of main.pdf]
Preview
Text - Published Version
Available under License Creative Commons: Attribution International Public License 4.0.

Download (670kB) | Preview

Export

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

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login