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


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

  1. Given n points in d, compute their minimum enclosing cylinder.
  2. Given two n-point sets in d dimensions, decide whether they can be separated by two hyperplanes.
  3. 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)nc) 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).

other papers about this subject
Last update: March 10, 2011.