Ph.D. thesis : On the computational complexity of some problems from discrete geometry in higher dimensions
Advisor: Prof. Dr. Günter Rote
In my thesis I will investigate computational aspects of problems from discrete geometry in higher dimensions. In case they turn out to be (NP)-hard, I will try to attack them using several different computational techniques and tools, such as parameterized complexity and approximation algorithms.
Among others, I am going to consider the following problems, all of which can be solved efficiently in the plane: ham-sandwich cuts, epsilon-nets and discrepancy, point-set congruence, Erdös-Szekeres type problems, and Tverberg- and center-points.