Algorithmische Geometrie / vieweg studium; Aufbaukurs Mathematik (PDF)

zu jeder Hyperebene dann definiert der Durchschnitt P = ki =1 H+ i ein (konvexes) Polyeder (siehe Abbildung 1.1 für ein Beispiel in R3).

Polyeder bilden ein geometrisches Grundkonzept für die algorithmische Geometrie und die lineare Optimierung. In hohen Dimensionen ist die kombinatorische Vielfalt von Polyedern erheblich größer als sich durch niedrigdimensionale Visualisierungen wie in Abbildung 1.1 erahnen lässt. Eine für die Komplexität vieler Algorithmen grundlegende Frage ist, wie viele Ecken ein durch k lineare Ungleichungen de.niertes Polyeder maximal haben kann. Dieser Sachverhalt wurde erst im Jahr 1970 durch das Upper-Bound-Theorem geklärt, dessen Beweis (in einer etwas abgeschwächten Version, siehe Satz 3.44) und die Klärung der zugrunde liegenden geometrischen Struktur ein erstes Etappenziel des Buches ist. Für die algorithmische Geometrie ist das Resultat von besonderer Bedeutung, weil sich hieraus Komplexitätsabschätzungen für einige Verfahren ergeben.

In Kapitel 3 studieren wir systematisch Eigenschaften von Polytopen (Seitenverband, Polarität, Kombinatorik von Polytopen) bis hin zur Euler-Formel und denDehn-Sommerville-Gleichungen.AmEnde des Kapitels illustrieren und visualisieren wir einige der Überlegungen mit der Geometrie-Software polymake. Diese wird auch in späteren Kapiteln zur Verdeutlichung der vorgestellten Algorithmen verwendet. Kernstück vielermathematischer Anwendungen ist die lineare Optimierung. Hierbei soll auf einem (durch lineare Ungleichungen gegebenen) Polyeder P das Minimum (bzw. Maximum) bezüglich einer linearen Zielfunktion bestimmt werden.

Für algorithmische Lösungen ist zudem zu beachten, dass das Polyeder leer sein kann, oder die Zielfunktion auf P unbeschränkt. In Kapitel 4 geben wir eine kompakte Einführung in die relevanten Aspekte der linearen Optimierung. Insbesondere diskutieren wir den sowohl theoretisch als auch praktisch wichtigen Simplex-Algorithmus.Dabei betonenwir – unserem Thema entsprechend – die geometrische Sichtweise.