The parameterized complexity of some geometric problems in unbounded dimension

Abstract

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^{\Omega (d)}$-time lower bound (under the Exponential Time Hypothesis).

Cited by in corpus (3)

• The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
• The limited blessing of low dimensionality: when $1-1/d$ is the best possible exponent for $d$-dimensional geometric problems
• Fixed Parameter Complexity and Approximability of Norm Maximization