On the Computational Complexity of some problems from Combinatorial Geometry

Abstract. We study several canonical decision problems that arise from the most famous theorems from combinatorial geometry. We show that these are W[1]-hard (and NP-hard) if the dimension is part of the input by fpt-reductions (which are actually ptime-reductions) from the d-Sum problem. Among others, we show that computing the minimum size of a Caratheodory set and a Helly set and certain decision versions of the Ham-Sandwich cut problem are W[1]-hard. Our reductions also imply that the problems we consider cannot be solved in time no(d) (where n is the size of the input), unless the Exponential-Time Hypothesis (ETH) is false. Our technique of embedding d-Sum into a geometric setting is conceptu-ally much simpler than direct fpt-reductions from purely combinatorial W[1]-hard problems (like the clique problem) and has great potential to show (parameterized) hardness and (conditional) lower bounds for many other problems