The Generalized Minimum Manhattan Network Problem

Abstract

In this thesis we consider the Generalized Minimum Manhattan Network Problem: given a set containing n pairs of points in R2 or Rd, the goal is to find a rectilinear network of minimal length which contains a path of minimal length (a so-called Manhattan path) between the two points of each pair. We restrict our search to a discrete subspace and show that under specific conditions an optimal solution can be found in polynomial time using a dynamic program. The conditions concern the intersection graph of the bounding boxes of the pairs. Its maximum degree as well as the treewidth must be bounded by two constants which are independent of n. Finally, we present a simple greedy algorithm for practical purposes.

Wir wollen in dieser Arbeit das verallgemeinerte Minimum-Manhattan-Netzwerk-Problem betrachten: Wir suchen, gegeben eine Menge von n Punktepaaren aus R2 oder Rd, ein achsenparalleles Netzwerk von kleinstmöglicher Gesamtlänge, das für jedes Paar jeweils einen sogenannten Manhattan-Pfad enthält, einen achsenparallelen Pfad minimaler Länge, der die beiden Punkte verbindet. Wir schränken die Suche auf einen diskreten Teilraum ein und zeigen, dass es unter bestimmten Voraussetzungen möglich ist, mittels eines dynamischen Programms in Polynomialzeit eine optimale Lösung zu finden. Die Voraussetzungen betreffen den Schnittgraph der Bounding-Boxen der Punktepaare. Sein Maximalgrad und seine Baumweite müssen durch zwei Konstanten beschränkt sein, die unabhängig von n sind. Zuletzt stellen wir einen einfachen Greedy-Algorithmus für die Anwendung in der Praxis vor.