Show simple item record

dc.contributor.authorBonnet, Edouard
dc.contributor.authorGiannopoulos, Panos
dc.contributor.authorLampis, Michael
dc.date.accessioned2020-07-22T14:42:29Z
dc.date.available2020-07-22T14:42:29Z
dc.date.issued2017
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20962
dc.language.isoenen
dc.subjectETH-based lower bounden
dc.subjectred-blue points separationen
dc.subjectgeometric problemen
dc.subjectW[1]-hardnessen
dc.subjectFPT algorithmen
dc.subject.ddc005en
dc.titleOn the Parameterized Complexity of Red-Blue Points Separationen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.citationpages8:1--8:13en
dc.relation.ispartofeditorLokshtanov, Daniel
dc.relation.ispartofeditorNishimura, Naomi
dc.relation.ispartofpublnameSchloss Dagstuhl--Leibniz-Zentrum fuer Informatiken
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-3-95977-051-4en
dc.relation.conftitle12th International Symposium on Parameterized and Exact Computation (IPEC 2017)en
dc.relation.confdate2017-09
dc.relation.confcityVienneen
dc.relation.confcountryAustriaen
dc.relation.forthcomingnonen
dc.identifier.doi10.4230/LIPIcs.IPEC.2017.8en
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2020-07-22T14:38:20Z
hal.person.labIds989
hal.person.labIds
hal.person.labIds989


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record