The Complexity of Geometric Problems in High Dimension

摘要

Many important NP-hard geometric problems in R~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 R~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.