Algorithmische Geometrie: Polyedrische und algebraische Methoden

✍ Scribed by Michael Joswig, Thorsten Theobald

• Publisher: Vieweg Friedr. + Sohn Verlag
• Year: 2007
• Tongue: German
• Leaves: 239
• Edition: 2008
• Category: Library

✦ Synopsis

In dem Lehrbuch wird eine mathematisch orientierte Einführung in die algorithmische Geometrie gegeben. Im ersten Teil werden „klassische“ Probleme und Techniken behandelt, die sich auf polyedrische (= linear begrenzte) Objekte beziehen. Hierzu gehören beispielsweise Algorithmen zur Berechnung konvexer Hüllen und die Konstruktion von Voronoi-Diagrammen. Im zweiten Teil werden grundlegende Methoden der algorithmischen algebraischen Geometrie entwickelt und anhand von Anwendungen aus Computergrafik, Kurvenrekonstruktion und Robotik illustriert. Das Buch eignet sich für ein fortgeschrittenes Modul in den derzeit neu konzipierten Bachelor-Studiengängen in Mathematik und Informatik.

✦ Table of Contents

Vorwort......Page 6
1.1 Lineare algorithmische Geometrie......Page 8
1.2 Nichtlineare algorithmische Geometrie......Page 11
1.3 Anwendungen......Page 13
Zur Organisation des Textes......Page 14
Teil I Lineare algorithmische Geometrie......Page 15
2.1 Projektive Räume......Page 16
2.2 Projektive Transformationen......Page 19
2.3 Konvexität......Page 21
2.4 Aufgaben......Page 23
2.5 Anmerkungen......Page 24
3.1 De.nitionen und grundlegende Eigenschaften......Page 25
3.2 Der Seitenverband eines Polytops......Page 31
3.3 Polarität und Dualität......Page 34
3.4 Polyeder......Page 38
3.5 Die Kombinatorik von Polytopen......Page 41
3.6 Untersuchungen mit polymake......Page 47
3.7 Aufgaben......Page 49
3.8 Anmerkungen......Page 50
4.1 Problemstellung......Page 51
4.2 Dualität......Page 53
4.3 Der Simplex-Algorithmus......Page 57
4.4 Bestimmen einer Startecke......Page 64
4.5 Untersuchungen mit polymake......Page 66
4.6 Aufgaben......Page 67
4.7 Anmerkungen......Page 68
5.1 Vorüberlegungen......Page 70
5.2 Die Methode der doppelten Beschreibung......Page 72
5.3 Ebene konvexe Hüllen......Page 78
5.4 Untersuchungen mit polymake......Page 82
5.5 Aufgaben......Page 83
5.6 Anmerkungen......Page 84
6.1 Voronoi-Regionen......Page 86
6.2 Polyedrische Komplexe......Page 88
6.3 Voronoi-Diagramme und konvexe Hüllen......Page 90
6.4 Der Wellenfront-Algorithmus......Page 93
6.5 Bestimmung des nächsten Nachbarn......Page 103
6.6 Aufgaben......Page 104
6.7 Anmerkungen......Page 105
Teil II Nichtlineare algorithmische Geometrie......Page 106
8.1 Motivation......Page 107
8.2 Univariate Polynome......Page 110
8.3 Resultanten......Page 112
8.4 Ebene af.ne algebraische Kurven......Page 114
8.5 Projektive Kurven......Page 116
8.6 Der Satz von Bézout......Page 118
8.7 Algebraische Kurven mit Maple......Page 122
8.8 Aufgaben......Page 124
8.9 Anmerkungen......Page 125
9.1 Ideale und der univariate Fall......Page 126
9.2 Monomordnungen......Page 130
9.3 Gröbnerbasen und der Hilbertsche Basissatz......Page 133
9.4 Der Algorithmus von Buchberger......Page 138
9.5 Binomiale Ideale......Page 141
9.6 Ein elementargeometrischer Beweis mit Gröbnerbasen......Page 142
9.7 Aufgaben......Page 144
9.8 Anmerkungen......Page 145
10.1 Gröbnerbasen mit Maple und Singular......Page 147
10.2 Elimination von Unbestimmten......Page 149
10.3 Fortsetzung partieller Lösungen......Page 152
10.4 Hilberts Nullstellensatz......Page 154
10.5 Lösen polynomialer Gleichungen......Page 158
10.6 Gröbnerbasen und ganzzahlige lineare Programme......Page 162
10.7 Aufgaben......Page 167
10.8 Anmerkungen......Page 168
Teil III Anwendungen......Page 169
11 Kurvenrekonstruktion......Page 170
11.2 Die mediale Achse und lokale Details......Page 171
11.3 Muster und polygonale Rekonstruktion......Page 174
11.4 Der Algorithmus NN-Crust......Page 177
11.5 Kurvenrekonstruktion mit polymake......Page 180
11.7 Anmerkungen......Page 182
12.1 Plücker-Koordinaten......Page 184
12.2 Äußere Multiplikation und äußere Algebra......Page 186
12.3 Dualität......Page 190
12.4 Rechnen mit Plücker-Koordinaten......Page 195
12.5 Geraden in R3......Page 196
12.7 Anmerkungen......Page 198
13.1 Voronoi-Diagramme für Geradensegmente in der Ebene......Page 199
13.2 Kinematische Probleme und Bewegungsplanungen......Page 202
13.3 Das Global Positioning System GPS......Page 210
13.4 Anmerkungen......Page 212
Teil IV Anhänge......Page 213
A.1 Gruppen, Ringe, Körper......Page 214
A.2 Polynomringe......Page 215
B Trennungssätze......Page 217
C.1 Komplexität von Algorithmen......Page 220
C.2 Die Komplexitätsklassen P und NP......Page 223
D.2 Maple......Page 226
D.4 CGAL......Page 227
E Notation......Page 228
Literaturverzeichnis......Page 230
Index......Page 235