Tillmann Miltzow

Geometric and Combinatorial Problems of Matching and Partitioning in Theoretical Computer Science

Betreuer: Prof. Dr. Günter Rote
Abschluss: PhD
Abgabedatum: 05.06.2015
Homepage des Autors:


In this thesis, we consider four problems in theoretical Computer Science:

1.Disjoint Unit Disks in the plane and disjoint unit balls in space can be separated by hyperplanes. Doing his, we try to minimize the number of intersections between the hyperplane and the balls. Although the first papers appeared in the 80s of the last century, up to now there existed no optimal deterministic algorithm to find such a hyperplane. We present an exact algorithm in the plane and approximate algorithm in higher dimensions. (This part is joint work with Michael Hoffman and Vincent Kusters.)

2. Tron is a computer game from the 80s of the last century, which was studied at first by Bodlaender and Kloks on abstract graphs. We answer questions that remained open regarding algorithmic complexity and study the minimal and maximal outcome of the game under the assumptions that both players play optimally. We consider these questions in different game modi.

3. Pareto Optimal Matchings are a concept used in economics and game theory. They describe certain stabil situations similar to Nash-equlibria. They also play a role in some algorithmic questions.
We give upper bounds on the number of Pareto Optimal Matchings under simple conditions. Further, we investigate a series of related algorithmic questions. (This part is joint work with Andrei Asinowski and Balázs Keszegh.)

4. Geometric Matchings are non-crossing segments connecting a set of points in the plane. Although it is very simple to find colored point sets admitting exactly one geometric matching, up to now there has been no characterization of such point sets in general. We give several simple and elegant characterization and answer further questions to this class of points. (This part is joint work with Andrei Asinowski und Günter Rote)