Master thesis : Optimale Manhattan-Netzwerke

Georgy Skyarenko

Advisor:

Ein Manhattan-Netzwerk für eine gegebene Punktmenge ist ein geometrischer Graph, der Manhattan-Wege für alle seinen Knotenpaare enthält, wobei ein Manhattan-Weg eine Geodetische in der L1-Metrik darstellt. In dieser Arbeit wird das Problem der Berechnung des Manhattan-Netzwerks mit einer minimalen Anzahl von Strecken und Steinerpunkten untersucht. Approximationsalgorithmen werden vorgestellt und ein ganzzahliges lineares Programm wird formuliert. Das Verhalten des integrality-Gap für das relaxierte Programm wird experimentell analysiert.