Source author record

Gunter Rote

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Computational Complexity

Catalog footprint

Research overview

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2009arXiv

Fixed-parameter tractability and lower bounds for stabbing problems

We study the following general stabbing problem from a parameterized complexity point of view: Given a set $\mathcal S$ of $n$ translates of an object in $\Rd$, find a set of $k$ lines with the property that every object in $\mathcal S$ is ''stabbed'' (intersected) by at least one line. We show that when $S$ consists of axis-parallel unit squares in $\Rtwo$ the (decision) problem of stabbing $S$ with axis-parallel lines is W[1]-hard with respect to $k$ (and thus, not fixed-parameter tractable unless FPT=W[1]) while it becomes fixed-parameter tractable when the squares are disjoint. We also show that the problem of stabbing a set of disjoint unit squares in $\Rtwo$ with lines of arbitrary directions is W[1]--hard with respect to $k$ . Several generalizations to other types of objects and lines with arbitrary directions are also presented. Finally, we show that deciding whether a set of unit balls in $\Rd$ can be stabbed by one line is W[1]--hard with respect to the dimension $d$ .

preprint2009arXiv

The parameterized complexity of some geometric problems in unbounded dimension

We study the parameterized complexity of the following fundamental geometric problems with respect to the dimension $d$ : i) Given $n$ points in $\Rd$, compute their minimum enclosing cylinder. ii) Given two $n$ -point sets in $\Rd$, decide whether they can be separated by two hyperplanes. iii) Given a system of $n$ linear inequalities with $d$ variables, find a maximum-size feasible subsystem. We show that (the decision versions of) all these problems are W[1]-hard when parameterized by the dimension $d$ . %and hence not solvable in ${O}(f(d)n^c)$ time, for any computable function $f$ and constant $c$ %(unless FPT=W[1]). Our reductions also give a $n^{Ω(d)}$ -time lower bound (under the Exponential Time Hypothesis).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.