In the modern world, geometric algorithms are all around us. They help us find the fastest route to work, they let us locate the nearest ATM, and they measure the similarity of visual patterns.

However, not for every task that we would like to accomplish with a geometric algorithm in practice, there is a known algorithm that is as fast and reliable as we would hope for. What is the reason for this? Does it just mean that we need to work harder in order to overcome our general ignorance, or is there a deeper reason behind our inability to come up with suitable algorithmic solutions?
The field in theoretical computer science that deals with this kind of questions is called computational complexity theory.

In this project, we would like to examine the complexity theoretic aspects of some popular problems from discrete and computational geometry. These problems are particularly suited for such an investigation for several reasons. On the one hand, they are relevant for widespread computational tasks such as route planning, nearest-neighbor search or mesh generation. On the other hand, there exists a deep and well-developed mathematical theory that provides a rich structure and a reservoir of techniques that we can tap into.

In particular, our plan is to consider problems that fall outside the traditional approach that was pursued in computational complexity theory. There, most work has focused on "decision problems", where we need to determine whether a solution to an algorithmic problem with certain properties exists. In this project, we are going to deal with "search problems", i.e., problems, where we can be sure that a solution with good properties is always at hand, but we do not know of any efficient method of finding it. The main objective of the project is to develop a new theory for these kind of questions that leads to a deeper understanding of both the algorithmic and the mathematical issues behind them.