License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2017.8
URN: urn:nbn:de:0030-drops-85687
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8568/
Go to the corresponding LIPIcs Volume Portal

Bonnet, Édouard ; Giannopoulos, Panos ; Lampis, Michael

On the Parameterized Complexity of Red-Blue Points Separation

pdf-format:
LIPIcs-IPEC-2017-8.pdf (0.6 MB)

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 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).

BibTeX - Entry

@InProceedings{bonnet_et_al:LIPIcs:2018:8568,
  author =	{{\'E}douard Bonnet and Panos Giannopoulos and Michael Lampis},
  title =	{{On the Parameterized Complexity of Red-Blue Points Separation}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Daniel Lokshtanov and Naomi Nishimura},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8568},
  URN =		{urn:nbn:de:0030-drops-85687},
  doi =		{10.4230/LIPIcs.IPEC.2017.8},
  annote =	{Keywords: red-blue points separation, geometric problem, W[1]-hardness, FPT algorithm, ETH-based lower bound}
}

Keywords: red-blue points separation, geometric problem, W[1]-hardness, FPT algorithm, ETH-based lower bound
Collection: 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Issue Date: 2018
Date of publication: 02.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI