dc.contributor.author Bonnet, Edouard dc.contributor.author Giannopoulos, Panos dc.contributor.author Lampis, Michael dc.date.accessioned 2020-07-22T14:42:29Z dc.date.available 2020-07-22T14:42:29Z dc.date.issued 2017 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/20962 dc.language.iso en en dc.subject ETH-based lower bound en dc.subject red-blue points separation en dc.subject geometric problem en dc.subject W[1]-hardness en dc.subject FPT algorithm en dc.subject.ddc 005 en dc.title On the Parameterized Complexity of Red-Blue Points Separation en dc.type Communication / Conférence dc.description.abstracten 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). en dc.identifier.citationpages 8:1--8:13 en dc.relation.ispartofeditor Lokshtanov, Daniel dc.relation.ispartofeditor Nishimura, Naomi dc.relation.ispartofpublname Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik en dc.subject.ddclabel Programmation, logiciels, organisation des données en dc.relation.ispartofisbn 978-3-95977-051-4 en dc.relation.conftitle 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) en dc.relation.confdate 2017-09 dc.relation.confcity Vienne en dc.relation.confcountry Austria en dc.relation.forthcoming non en dc.identifier.doi 10.4230/LIPIcs.IPEC.2017.8 en dc.description.ssrncandidate non en dc.description.halcandidate non en dc.description.readership recherche en dc.description.audience International en dc.relation.Isversionofjnlpeerreviewed non en dc.relation.Isversionofjnlpeerreviewed non en dc.date.updated 2020-07-22T14:38:20Z hal.person.labIds 989 hal.person.labIds hal.person.labIds 989
﻿