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

Abstract

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)

In dieser Arbeit betrachten wir vier Probleme der Theoretischen Informatik: 1\. Disjunkte Einheitsscheiben in der Ebene und disjunkte Einheitskugeln im Raum lassen sich durch Hyberebenen separieren. Dabei wird versucht die Anzahl der Schnitte von der Ebene mit den Objekten zu minimieren. Obwohl erste Arbeiten dazu in den 80er Jahren des letzten Jahrhunderts entstanden, gab es bis dato noch keinen optimalen deterministischen Algorithmus um solch eine Hyperebene zu finden. Wir stellen einen exakten Algorithmus in der Ebene und einen approximativen Algorithmus in höheren Dimensionen vor. (Dieser Teil entstand gemeinsam mit Michael Hoffman und Vincent Kusters.) 2\. Tron ist ein Computerspiel aus den 80er Jahren, das zunächst von Bodlaender und Kloks auf abstrakten Graphen studiert wurde. Wir beantworten offen geblieben Fragen zur algorithmischen Komplexität und untersuchen das maximal und minimale Punktunteverhältnis der beiden Spieler bei rationaler Spielweise. (Beide Spieler erzielen im Laufe des Spieles Punkte.) Wir betrachten diese Fragen in verschiedenen Spielmodi. 3\. Pareto Optimale Matchings kommen aus der Ökonomie und Spieletheorie und beschreiben bestimmte "stabile" Situationen ähnlich einem Nash-Equilibrium. Sie spielen auch in algorithmischen Problemen eine Rolle. Wir geben eine obere Schranke für die Anzahl für Pareto Optimale Matchings unter einfachen Nebenbedingungen an. Desweiteren lösen wir eine Reihe verwandter algorithmischer Probleme. (Dieser Teil entstand gemeinsam mit Balázs Keszegh und Andrei Asinowski.) 4\. Geometrische Matchings sind kreuzungsfreie Strecken, die eine Menge von Punkten in der Ebene verbinden. Obwohl es sehr einfach ist gefärbten Punktmengen mit nur einem einzigen geometrischen Matching zu finden, gelang es erst jetzt solche Punktmengen allgemein zu charakterisieren. Weitere Fragen zu dieser Klasse von Punktmengen wurden beantwortet. (Dieser Teil entstand gemeinsam mit Andrei Asinowski und Günter Rote.)