Selected topics in algorithmic geometry

Abstract

Let P be a set of n points on the plane with no three points on a line. A crossing-free structure on P is a straight-edge plane graph whose vertex set is P. In this thesis we consider problems of two different topics in the area of algorithmic geometry: Geometry using Steiner points, and counting algorithms. These topics have certain crossing-free structures on P as our primary objects of study. Our results can roughly be described as follows: i) Given a k-coloring of P, with k >= 3 colors, we will show how to construct a set of Steiner points S = S(P) such that a k-colored quadrangulation can always be constructed on (P U S). The bound we show of |S| significantly improves on previously known results. ii) We also show how to construct a se S = S(P) of Steiner points such that a triangulation of (P U S) having all its vertices of even (odd) degree can always be constructed. We show that |S| <= n/3 + c, where c is a constant. We also look at other variants of this problem. iii) With respect to counting algorithms, we show new algorithms for counting triangulations, pseudo-triangulations, crossing-free matchings and crossing-free spanning cycles on P. Our algorithms are simple and allow good analysis of their running times. These algorithms significantly improve over previously known results. We also show an algorithm that counts triangulations approximately, and a hardness result of a particular instance of the problem of counting triangulations exactly. iv) We show experiments comparing our algorithms for counting triangulations with another well-known algorithm that is supposed to be very fast in practice.

Sei P eine Menge von n Punkte in der Ebene, so dass keine drei Punkten auf einer Geraden liegen. Eine kreuzungsfreie Struktur von P ist ein geradliniger ebener Graph, der P als Knotenmenge hat. In dieser Dissertation behandeln wir zwei verschiedene Problemkreise auf dem Gebiet der algorithmischen Geometrie: Geometrie mit Steinerpunkten und Anzahl bestimmende Algorithmen auf P und auf gewissen kreuzungsfreien Strukturen von P. Unsere Resultate können wie folgt beschrieben werden: i) Gegeben sei eine k-Färbung von P, mit k >= 3 Farben. Es wird gezeigt, wie eine Menge S = S(P) von Steiner Punkten konstruiert werden kann, die die Konstruktion einer k-gefärbten Quadrangulierung von (P U S) ermöglicht. Die von uns gezeigte Schranke für |S| verbessert die bisher bekannte Schranke. ii) Gezeigt wird auch die Konstruktion einer Menge S = S(P) von Steiner Punkten, so dass eine Triangulierung von (P U S) konstruiert werden kann, bei der der Grad aller Knoten gerade (ungerade) ist. Wir zeigen, dass |S| <= n/3 + c möglich ist, wobei c eine Konstante ist. Wir betrachten auch andere Varianten dieses Problems. iii) Was die Anzahl bestimmenden Algorithmen betrifft, zeigen wir neue Algorithmen, um Triangulierungen, Pseudotriangulierungen, kreuzungsfreie Matchings und kreuzungsfreie aufspannende Zyklen von P zu zählen. Unsere Algorithmen sind einfach und lassen eine gute Analyse der Laufzeiten zu. Diese neuen Algorithmen verbessern wesentlich die bisherigen Ergebnisse. Weiter zeigen wir einen Algorithmus, der Triangulierungen approximativ zählt, und bestimmen die Komplexitätsklasse einer bestimmten Variante des Problems des exakten Zählens von Triangulierungen. iv) Wir zeigen Experimente, die unsere triangulierungszählenden Algorithmen mit einem anderen bekannten Algorithmus vergleichen, der in der Praxis als besonders schnell bekannt ist.