Ab- | Inhalt Vorlesung "Algorithmische Geometrie" | Seitenzahl |
| Inhaltsverzeichnis | 1, 2 | |
| 1 | Konvexe Hüllen | |
| 1.1 | Konstruktion der konvexen Hülle einer Punktmenge im TR² | 3, 4, 5, 6, 7, 8 |
| 1.2 | Schnitt von n Halbebenen mit Anwendung von Convex Hull | 9, 10, 11, 12 |
| 2 | Konvexe Polygone | |
| 2.1 | Hierarchische Darstellung | 13, 14 |
| 2.2 | Anwendung I: Schnitt Polygon/Gerade | 14, 15, 16 |
| 2.3 | Anwendung II: Schnitt Polygon/Polygon | 16, 17, 18 |
| 3 | Das Plane Sweep Verfahren | |
| 3.1 | Einleitung | 19 |
| 3.2 | Anwendung I: Schnitt von Segmenten | 19, 20, 21, 22, 23 |
| 3.3 | Anwendung II: Post Office Probleme | 24, 25, 26, 27, 27, 28, 29, 30, 31, 32 |
| 4 | Bewegungsplanung in der Ebene | |
| 4.1 | Problem I: S: Menge von Liniensegmenten, R: Kreisscheibe | 33, 34 |
| 4.2 | Problem II: S: Menge konvexer Polygone. R: konvexes Polygon | 35, 36, 37, 38, 39 |
| 5 | Geometrische Datenstrukturen | |
| 5.1 | Der Segmentbaum | 40, 41 |
| 5.2 | Der Range-Tree (Bereichsabfragebaum) | 42, 43 |
| 5.3 | Bemerkungen | 43 |
| 5.4 | Der Priority-Search-Tree | 44 |
| 6 | Anwendungen | |
| 6.1 | Das Maß-Problem für achsenparallele Rechtecke | 45, 46, 47 |
| 6.2 | 3-dim konvexe Hüllen | 48, 49, 50, 51 |
| 6.3 | Berechnung der Delaunay-Triangulierung | 51, 52 |
| 6.4 | 2 Anwendungen von Dualität | 52, 53, 54 |
| 6.5 | Berechnung des Arrangements von n Geraden | 54, 55 |
