Banner der Website mathematik.de. Motiv: Überall ist Mathematik

Der Diskrete Charme der Geometrie

von Günter M. Ziegler

Fachbereich Mathematik, MA 6-2, TU Berlin, 10623 Berlin
ziegler@math.tu-berlin.de

Einleitung

"Können Sie in zwei Sätzen erklären ...?" fangen beliebte Journalisten-Fragen an. Kann ich nicht - zumindest, was den "technischen Kern" meiner Entdeckungen, Untersuchungen und Erkundungen angeht. Mathematik ist eben doch eine komplizierte Sache. Sie ist eben vielfältig, hochentwickelt und weitverzweigt.

Ich beschäftige mich mit Problemen der linearen und diskreten Optimierung (die sich im "wirklichen Leben" in Busfahrplänen und in (nicht-)überlasteten Mobilfunknetzen wiederspiegeln), mit Fragen der diskreten Geometrie (die den Bogen von der Struktur der vier-dimensionalen Polyeder bis zu Anwendungen in der Computergraphik und dem Computer Aided Design spannen), und mit der Topologie von diskreten Strukturen (was Hilfsmittel dafür liefert, zu messen, ob ein Objekt "stark zusammenhängt" oder "niedrig- oder hoch-dimensionale Löcher oder Defekte hat").

Viele Ideen in diesen Untersuchungen sind einfach und geometrisch; die technische Durchführung basiert auf akkumuliertem Wissen aus Lehrbüchern, Vorlesungen, alter oder ganz neuer Fachliteratur, und oft am entscheidenden Punkt auf einem Gespräch mit einem Mitarbeiter oder Kollegen, in dem einem Verbindungen klar werden zwischen Dingen, die gerade eben noch gedanklich "weit auseinander lagen".

"In zwei Sätzen zusammenfassen" lassen sich solche mathematische Erkundungen nicht. Aber ein paar der Pretiosen herzeigen, das kann ich versuchen. Voilà, zwei Beispiele:

Die Geometrie der Polytope

Drei-dimensionale Polytope sind anschauliche und allgegenwärtige Objekte, die man nicht nur aus der griechischen Mathematik, sondern auch aus der Architektur, den Ingenieurwissenschaften, der Kristallographie usw. kennt. Die regelmäßigen Polytope sind schon von den Griechen klassifiziert worden, und sind als die "Platonischen Körper" bekannt.

Abbildung 1: Die regelmäßigen drei-dimensionalen Polytope

Noch interessanter, spannender und schöner finden viele Mathematiker die vier-dimensionalen Polytope, die man in der Form von drei-dimensionalen Projektionen, den so genannten Schlegel-Diagrammen, darstellen kann. (Vier-dimensionale Objekte erscheinen uns zunächst fremd; die mathematischen Werkzeuge zum Konstruieren, Beschreiben und Untersuchen solcher Objekte stellt jedoch die Vorlesung "Lineare Algebra" im ersten Studienjahr des Mathematikers zur Verfügung ...)

Abbildung 2: Ein Schlegel-Diagramm von einem 24-Zell (Mit polymake [3] und javaview [5] erzeugt)

Im vier-dimensionalen Raum gibt es viele bemerkenswerte Effekte, die im drei-dimensionalen Raum nicht möglich sind - beispielsweise kann man Polytope mit beliebig vielen Ecken konstruieren, für die jedes Eckenpaar durch eine Kante verbunden ist: so genannte nachbarschaftliche Polytope. Anders gesagt: Diese vier-dimensionalen Polytope haben dieselbe Ecken-Kanten-Struktur wie ein (n-1)-dimensionaler Tetraeder, der ja auch n Ecken und alle Verbindungskanten zwischen diesen hat.

Gibt es auch vier-dimensionale Polytope mit derselben Ecken-Kanten-Struktur, wie ein n-dimensionaler Würfel? Die Antwort ist "ja!" - die Konstruktion solcher Objekte gelang uns 1998, und ist in [4] dokumentiert.

Abbildung 3: Schlegel-Diagramm von einem vier-dimensionalen Polytop mit der Ecken-Kanten-Struktur eines fünf-dimensionalen Würfels

Nachdem dies gelungen war (die Konstruktion ist für n = 5 einfach, aber für große n ziemlich trickreich), stellte sich heraus, dass die Existenz der nachbarschaftlichen kubischen Polytope, die wir da gerade konstruiert hatten, gleich ein halbes Dutzend weiterer offener Probleme löste - zum Beispiel die Frage aus dem Computer-Aided Design (CAD), ob es Würfelzerlegungen im drei-dimensionalen Raum geben kann, für die die Anzahl der Würfel viel größer ist als die Anzahl der Ecken.

Pfade auf Polytopen und Simplex-Algorithmus

Der Simplex-Algorithmus ist ein Optimierungsverfahren von immenser kommerzieller Bedeutung, weil sich verschiedenste Planungs-, Steuerungs- und Optimierungsprobleme als lineare Programme formulieren lassen, und dann durch den Simplex-Algorithmus gelöst werden können. Praktisch funktioniert dieser Algorithmus inzwischen hervorragend - aber trotzdem ist seine Analyse ("Warum läuft er meistens so schnell?") immer noch eine "harte Nuss" für die Theoretiker.

In der geometrischen Interpretation von linearen Programmen geht es darum, auf einem d-dimensionalen Polytop, das durch n lineare Ungleichungen gegeben ist, die höchste Ecke zu finden. Der Simplex-Algorithmus macht das so, dass er sich erst mal irgendeine Ecke sucht, und von dieser ausgehend dann die Kanten entlangläuft - immer weiter "nach oben". Aber: Wie soll man an den Ecken jeweils die nächste Kante "nach oben" auswählen, wenn es mehrere gibt? Kann irgendeine Regel garantieren, dass man schnell zur höchsten Ecke kommt? Gibt es überhaupt immer einen kurzen Weg zur höchsten Ecke? (Das ist die berühmte "Hirsch-Vermutung" von 1957, immer noch ungelöst.)

Abbildung 4: Ein möglicher Weg "nach oben", den der Simplex-Algorithmus nehmen könnte

Nun, ich bin überzeugt, dass es eine gute Regel gibt: nämlich die Regel "Wähle zufällig eine Kante, die nach oben führt!" Diese random_edge-Regel scheint gut zu funktionieren - aber beweisen kann das immer noch niemand. In [2] ist es uns immerhin gelungen, die random_edge-Regel auf den vielleicht interessantesten ("ekligsten") Beispielen zu analysieren, die man in der Theorie der linearen Optimierung kennt: Die so genannten Klee-Minty-Würfel sind n-dimensionale Polytope, die wie leicht verzogene n-Würfel aussehen, und die die merkwürdige Eigenschaft haben, dass es einen aufsteigenden Pfad durch alle 2n Ecken gibt. (Solche Polytope lassen sich nach einem in [1] angegebenen allgemeinen Konstruktionsverfahren als "deformierte Produkte" erzeugen.) Nun lassen wir den Simplex-Algorithmus mit der random_edge-Regel auf den Klee-Minty-Würfeln laufen - wie lang wird er brauchen?

Abbildung 5: Ein drei-dimensionaler Klee-Minty-Würfel

Das ist ein hoch-dimensionales geometrisches Problem; aber es lässt sich auf ein rein kombinatorisches Modell reduzieren, indem man die Ecken des n-dimensionalen Würfels durch Ziffernfolgen aus n Nullen und Einsen kodiert. Damit erhält man einen Zufallsprozess, den wir das "Klee-Minty-Spiel" genannt haben, und das folgendermaßen funktioniert. Beginne mit einer zufälligen 0/1-Folge von n Nullen und Einsen, zum Beispiel mit

11010100010101010111001
und in jeder Runde wählen wir dann eine zufällige Eins - wir würfeln eine aus -, ändern sie in eine Null, und alle Ziffern rechts davon ändern wir auch, aus den Nullen machen wir Einsen und umgekehrt. Dabei kann in den ersten fünf Runden zum Beispiel das Folgende entstehen (die Eins, die wir ausgewürfelt haben, ist jeweils fett gedruckt):
11010100010101010111001
11010100001010101000110
11010100001010010111001
10101011110101101000110
10101011001010010111001
10101010110101101000110
...   ...   ...   ...   ...
Nun kann man sich überlegen, dass das Spiel immer nach endlich vielen Schritten endet, dass man nämlich irgendwann eine Zeile mit nur Nullen erhält. Aber wie schnell? Wenn's schlecht läuft, braucht man fast 2n Schritte. Wenn's gut läuft, nur ein paar. Im Erwartungswert braucht man "fast quadratisch viele Schritte": n2/7 scheint eine gute Schätzung für die Schrittzahl zu sein. Das war bemerkenswert trickreich zu beweisen [2]. Als es geschafft war, lieferte es aber auch die erste nicht-triviale untere Schranke für die Laufzeit des random_edge-Simplex-Algorithmus; und die ist bisher nicht verbessert worden ...

Wir verlassen hier den Kurzbericht vom Zusammenspiel zwischen der Geometrie der Polytope, Linearer Optimierung und kombinatorischen Spielen - und verweisen auf [6] für mehr, insbesondere für mehr spannende ungelöste Probleme über die diskrete Geometrie der Polytope.

Literatur

[1]
N. Amenta & G. M. Ziegler: Deformed products and maximal shadows, in: ``Advances in Discrete and Computational Geometry" (B. Chazelle, J.E. Goodman, R. Pollack, eds.), Contemporary Math. 223 (1998), 57-90.

[2]
B. Gärtner, M. Henk & G. M. Ziegler: Randomized simplex algorithms on Klee-Minty cubes, Combinatorica 18 (1998), 349-372.

[3]
E. Gawrilow & M. Joswig: polymake 1.4, http://www.math.tu-berlin.de/diskregeom/polymake, December 2000.

[4]
M. Joswig & G. M. Ziegler: Neighborly cubical polytopes, in: ``Grünbaum Festschrift" (G. Kalai, V. Klee, eds.), Discrete Comput. Geometry 24 (2000), 325-344.

[5]
K. Polthier, S. Khadem-Al-Charieh, E. Preuß & U. Eitebuch: JavaView - 3D Geometry in Web Pages, http://www.javaview.de, June 2000.

[6]
G. M. Ziegler: Questions about polytopes, in: ``Mathematics Unlimited - 2001 and Beyond" (B. Enquist, W. Schmid, eds.), Springer-Verlag, Heidelberg 2001, 1195-1211.




File translated from TEX by TTH, version 2.79.
On 16 Jan 2001, 14:25.