Ph.D. thesis : Dominanzprobleme für Punktmengen
Lorenz Wernisch
Advisor:
Gegeben seien n Punkte in der Ebene. Dabei dominiert ein Punkt x einen anderen y , wenn x sich, anschaulich gesprochen, rechts oben von y befindet. Eine Kette in X ist eine Teilmenge von X , worin von zwei Punkten immer einer den anderen dominiert. Eine maximale k-Kette ist eine Vereinigung von k Ketten mit den meisten Elementen unter allen solchen Vereinigungen (siehe Abb. 1). Die Arbeit beschreibt einen Algorithmus, der eine solche k -Kette in Zeit O (k n log n) berechnet ( n die Größe von X ). Dieses Problem hat einige Anwendungen, unter anderem im VLSI Design und in der algorithmischen Geometrie.
Dieser und verwandte Algorithmen beruhen auf Viennots Konstruktion von Skeletten. Die Arbeit gibt eine Einführung in diese Theorie. Klassische Resultate werden durchgehend geometrisch bewiesen. Weiters wird die erwartetete Größe einer maximalen k -Kette in einer Menge von zufälligen Punkten berechnet.
Der Begriff der Dominanzordnung bleibt sinnvoll, wenn man Punkte in höherdimensionalen Räumen betrachtet, oder Punkte durch achsenparallele Rechtecke ersetzt. Für diese Gebilde wird selbst die Berechnung einfacher Ketten schwierig. Die Berechnung von Ketten und Antiketten (d.h. von Teilmengen, worin kein Punkt irgendeinen anderen dominiert) für zweidimensionale Mengen von Rechtecken ist aber in optimaler Zeit möglich (selbst wenn man diese Punkte gewichtet).