Anna Schulze
Zentrum für Angewandte Informatik Köln
Universität zu Köln

Approximationen für Manhattan Netzwerke

Es wird eine 3- und eine 2-Approximation für das Manhattan-Netzwerk Problem mit Laufzeit O(n\log n) bzw. O(n3) vorgestellt. Die beiden Algorithmen bestehen jeweils aus zwei Teilen. Im ersten Teil wird für jede der beiden zulässigen Richtungen mit Hilfe eines Sweep-Verfahrens eine Menge von Kanten berechnet. Diese sogenannten Basiskanten garantieren, dass die zu verdrahtende Ebene in Flächen partitioniert wird, deren Ränder aus den berechneten Kanten bestehen. Im zweiten Teil wird für jede dieser Flächen ein Manhattan-Netzwerk berechnet. Auf Grund der Struktur der Flächen kann dies effizient gelöst werden. Mit den so berechneten Kanten erhält man ein Manhattan-Netzwerk. Der Unterschied zwischen den beiden Algorithmen besteht hauptsächlich in differierenden Basiskantenmengen, die im ersten Teil der Algorithmen berechnet werden. Bei der 3-Approximation werden mehr Basiskanten als bei der 2-Approximation berechnet. Dadurch erhalten wir den etwas schlechteren Approximationsfaktor. Andererseits wird dadurch die Struktur der Flächen einfacher, so dass wir für die Flächen effizienter Manhattan-Netzwerke berechnen können. Somit erhalten wir für die 3-Approximation eine bessere Laufzeit als die der 2-Approximation.