Algorithmische Geometrie

Michael Joswig und Thorsten Theobald

This is a description of the contents of a book on algorithmic geometry (in German). It features elements both from linear/convex geometry and algebraic/non-linear geometry.

Das Buch ist 2008 im Vieweg-Verlag erschienen. Auf dieser Seite stellen wir Zusatzmaterial bereit.

Inhalt

1. Einführung und Überblick

Teil I: Lineare algorithmische Geometrie

2. Geometrische Grundlagen
3. Polytope und Polyeder
   • polymake-Dateien (und jpg): zufällige Polytope mit acht [poly] [jpg], 100 [poly] [jpg] und 1000 [poly] [jpg] Ecken
   • zyklisches 4-Polytop mit sieben Ecken [poly]
4. Lineare Optimierung
5. Berechnung konvexer Hüllen
6. Voronoi-Diagramme
7. Delone-Triangulierungen
   • polymake-Datei (und jpg): Voronoi-Diagramm und Delone-Zerlegung zu zehn Postämtern in Berlin [vor] [jpg]

Teil II: Nichtlineare algorithmische Geometrie

8. Algebraische und geometrische Grundlagen
   • Maple worksheet und Ausgabe zu Abschnitt 8.6, Satz von Bézout
9. Gröbnerbasen und der Buchberger-Algorithmus
10. Lösen polynomialer Gleichungssysteme mit Gröbnerbasen

Teil III: Anwendungen

11. Kurvenrekonstruktion
12. Plücker-Koordinaten und Geraden im Raum
13. Anwendungen der nichtlinearen algorithmische Geometrie

Anhänge

1. Algebraische Strukturen
2. Trennungssätze
3. Algorithmen und Komplexität
4. Software
   • polymake
   • Maple
   • Singular
   • CGAL