|
| | | | |
| | | |
| Stat |
Members: 3644
Articles: 2'499'343
Articles rated: 2609
16 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
On the Parameterized Complexity of Red-Blue Points Separation | | Édouard Bonnet
; Panos Giannopoulos
; Michael Lampis
; | | Date: |
2 Oct 2017 | | 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). | | Source: | arXiv, 1710.0637 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER