Panos Giannopoulos, Christian Knauer, and Günter Rote:
The parameterized complexity of some geometric problems in unbounded
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,
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
- 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-hard
when parameterized by the dimension d, and hence not solvable
in O(f(d)nc) time, for any computable function f and
constant c (unless FPT=W). Our reductions also give an
nΩ(d)-time lower bound (under the Exponential Time
Last update: March 10, 2011.