## Panos Giannopoulos, Christian Knauer, and Günter Rote:

# The parameterized complexity of some geometric problems in unbounded
dimension

*In: Proc. 4th Int. Workshop on Parameterized and Exact
Computation-IWPEC 2009, Copenhagen, September 2009, Editors: Jianer
Chen and Fedor V. Fomin, Lecture Notes in Computer Science,
Vol. 5917, Springer-Verlag, 2009, pp. 198–209. *doi:10.1007/978-3-642-11269-0_16,
arXiv:0906.3469 [cs.CG].
### Abstract

We study the parameterized complexity of the following fundamental geometric
problems with respect to the dimension `d`:

- Given
`n` points in `d`, compute their minimum enclosing
cylinder.
- Given two
`n`-point sets in `d` dimensions,
decide whether they can be separated by two hyperplanes.
- 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 an
`n`^{Ω(d)}-time lower bound (under the Exponential Time
Hypothesis).

Last update: March 10, 2011.