We will investigate computational aspects of several problems from discrete geometry in higher dimensions. In the plane, many of them are well understood and can be solved efficiently, but as the dimension increases, most of them seem to be considerably harder to solve. In this thesis, we make progress towards explaining this phenomenon by showing computational hardness for some of these problems. To this end, we also make use of parameterized complexity theory in order to show stronger relative lower bounds than those possible with classical complexity theory only. For one of the problems, we moreover develop several approximation algorithms. In the process, we pay particular attention to the exact dependence of the running time on the dimension.

We will use and develop different techniques for showing hardness of the problems in unbounded dimension. These include the technique of deconstructing the space into orthogonal planes, into which gadgets are placed. Using this technique, we are able to show a relative lower bound of n^Omega(d) for several problems related to testing the discrepancy of a point set and verifying epsilon-nets.

We then present a more natural reduction technique that reduces from the d-Sum problem to show relative lower bounds for many problems arising from theorems in combinatorial geometry. These include computing minimal Helly sets, certain decision versions of the ham-sandwich problem, and computing the Tverberg depth of a point set.

We then turn to computing a maximum size subset of points in convex position. While all the previous problems admit straightforward n^O(\poly(d)) algorithms in d dimensions, here we are able to show that the problem already becomes hard in 3 dimensions. This shows a strong dichotomy between a low and a higher dimensional case, because in the plane the problem was known to be solvable in polynomial time.

As a positive result, we then consider the problem of computing a point of high Tverberg depth in d dimensions. We present a novel lifting approach that allows us to compute deep points for a point set in high dimension from deep points of its projection to some lower dimensional space. The approach is very generic, and we show how to combine it with other known methods in order to get even better algorithms.

Finally, we give a short outlook and suggest further open problems on the subject.