Abschnitt | Inhalt Vorlesung "Algorithmische Geometrie" | Seitenzahl |
| Inhaltsverzeichnis | 1, 2, 3, 4, 5, 6, 7 | |
| Definition "Algorithmische Geometrie" | 8 | |
| 1 | Konvexe Hüllen | |
| 1.1 | Konstruktion einer konvexen Hülle einer Punktmenge im R² | 9 |
| 1.2 | Algorithmus I: Gift Wrapping | 10, 11 |
| 1.3 | Algorithmus II: Graham's Scan | 12, 13, 14, 15 |
| 1.4 | Algorithmus III: Devide and Conquer | 15,16 |
| 1.5 | Eine Anwendung von Convex Hull | 16, 17, 18, 19, 20, 21, 22 |
| 2 | Konvexe Polygone | |
| 2.1 | Einführung | 23, 24, 25 |
| 2.2 | Anwendung der hierarchischen Darstellung | 24, 26, 27, 28, 29 |
| 2.3 | Weiteres Problem auf konvexen Polygonen | 29, 30, 31, 32, 33 |
| 3 | Das Plane Sweep Verfahren | |
| 3.1 | Einführung | 34 |
| 3.2 | Erste Anwendung: Line Segment Intersection | 34, 35, 36, 37, 38, 39 |
| 3.3 | Zweite Anwendung: Schnitt von beliebigen Polygonen | 40 |
| 3.4 | Dritte Anwendung: Berechnung des Voronoi-Diagramms | 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56 |
| 4 | Bewegungsplanung in der Ebene | |
| 4.1 | Einführung | 57 |
| 4.2 | Problem 1: R ist Kreis und S Menge von Segmenten | 57, 58, 59 |
| 4.3 | Problem 2: R ist konvexes Polygon und S Menge von konvexen Polygonen | 60, 61, 62, 63, 64, 65, 66, 67, 89, 90 |
| 5 | Geometrische Datenstrukturen | |
| 5.1 | Segmentbaum | 68, 69, 70, 71 |
| 5.2 | Range Tree (Bereichsabfragebaum) | 71, 72, 73, |
| 5.3 | Priority - Search-Tree | 74, 75 |
| 5.4 | Das Maßproblem für achsenparallele Rechtecke | 76, 77, 78 |
| 6 | Dreidimensionale konvexe Hüllen | |
| 6.1 | Einführung | 79, 80 |
| 6.2 | Algorithmen | 80, 81, 82, 83 |
| 6.3 | Anwendung von 3d-konvexen Hüllen | 83, 84 |
| 6.4 | Arrangements und Dualität | 84, 85, 86, 87, 88 |
