Many important NP-hard geometric problems in ℝ
d
are trivially solvable in time n
O(d) (where n is the size of the input), but such a time dependency quickly becomes intractable for higher-dimensional data, and thus it
is interesting to ask whether the dependency on d can be mildened. We try to adress this question by applying techniques from parameterized complexity theory.
More precisely, we describe two different approaches to show parameterized intractability of such problems: An “established”
framework that gives fpt-reductions from the k-clique problem to a large class of geometric problems in ℝ
d
, and a different new approach that gives fpt-reductions from the k-Sum problem.
While the second approach seems conceptually simpler, the first approach often yields stronger results, in that it further
implies that the d-dimensional problems reduced to cannot be solved in time n
o(d), unless the Exponential-Time Hypothesis (ETH) is false.
Keywords parameterized complexity - geometric dimension - lower bounds - exponential-time hypothesis
This research was supported by the German Science Foundation (DFG) under grant Kn 591/3-1.